Print power of string/array-CodePudding

Given an integer array nums of unique elements, return all possible subsets (the power set). The belwo code is returning wrong answer for input [1,2].How to fix it?

Expected Output is

[[],[1],[2],[1,2]]

I have written the code here which works fine.But i wanted to know why we are doing https://leetcode.com/submissions/detail/735373452/

output.remove(output.size()-1);

But in the same code i don't do backtrack but it still print all power sets

String s = "ABC";
                ps(s, 0, "");
public static void ps(String str, int i, String ans) {

        if (i == str.length()) {
            System.out.println(" Print "   ans);

            return;
        }

        ps(str, i   1, ans   str.charAt(i));
        ps(str, i   1, ans);

    }

CodePudding user response：

In short, you are creating 2 ^ n Strings during the recursive call, where n is the length of str. While the code in leetcode is using a single List. Adding elements to the List will have influence after the method call, thus need to remove the element to "restore" the List.

In Java, Strings are immutable. In your recursive ps function, you are creating new Strings with ans str.charAt(i), the original ans remains the same. Therefore you don't need to use the backtracking.

// say ans == "A", and str.charAt(1) == "B":

ps(str, i   1, ans   str.charAt(i));
ps(str, i   1, ans);

// will be called as:
ps("ABC", 2, "AB");
ps("ABC", 2, "A");

In the leetcode code, it's using a List. All the recursive calls share the same List. Modifying the list will impact the following calls. If we add an element before calling the function, we need to remove the element after calling the function.

// ans is a List now, not String: ans == ['A', 'B']
ans.add(str.charAt(i));   // ans == ['A', 'B', 'C']
ps(str, i   1, ans);  // ps("ABC", 3, ['A', 'B', 'C'])

// ans is still ['A', 'B', 'C']
// we want to call ps("ABC", 3, ['A', 'B']) now:
ans.remove(ans.size() - 1);
ps(str, i   1, ans);

Perhaps you are thinking that maybe changing the order will work:

ps(str, i   1, ans);

ans.add(str.charAt(i));
ps(str, i   1, ans);

It still has the problem if not calling ans.remove(str.charAt(ans.size() - 1). You can try changing the type of ans to List<Character> or StringBuilder in your ps function, and print ans during each recursive call.