Power Set Using Recursion

PHOTO EMBED

Sun Feb 06 2022 23:27:01 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #recursion #powerset

class LexSort
{
    static void solve(String s,String out, ArrayList<String> ans ,int i){
        if(i==s.length()){
            ans.add(out);
            return;
        }
        char ch=s.charAt(i);
        solve(s,out,ans,i+1);
        solve(s,out+String.valueOf(ch),ans,i+1);
    }
    
    //Function to return the lexicographically sorted power-set of the string.
    static ArrayList<String> powerSet(String s)
    {
        ArrayList<String> ans= new ArrayList<>();
        solve(s,"",ans,0);
        return ans;
    }
}
content_copyCOPY

Power Set Using Recursion You are given a string. You need to print the lexicographically sorted power-set of the string. Note: The string s contains lowercase letter of alphabet. Example 1: Input: s = a Output: a Explanation: empty string and a are only sets. Example 2: Input: s = abc Output: a ab abc ac b bc c Explanation: empty string, a, ab, abc, ac, b, bc, c are the sets. Your Task: You don't need to read input or print anything. You only need to complete the function powerSet that takes string s as parameter and returns a list of subsets. The lexicographic-sorting and printing is done automatically by the driver code. Expected Time Complexity: O(2^|s|). Expected Auxiliary Space: O(|s|). Constraints: 1 <= |s| <= 10

https://practice.geeksforgeeks.org/problems/power-set-using-recursion/1/?track=DSASP-Recursion&batchId=190