Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Example :
If S = [1,2,2], the solution is:

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

Method:

Because there is duplicates, we can't simply decide whether to add an element in each level, and use the last level as result, that way we get duplicate results. Instead, we generate solution in the middle of the recursion, and skip duplicate number on the same level of recursion to avoid duplicates.

Solution:

Time: O(2^n)
Space: O(2^n)

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> A) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> current = new ArrayList<>();
        result.add(current);
        Collections.sort(A);
        helper(result, current, A, 0);
        return result;
    }
    
    private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> current, ArrayList<Integer> A, int index) {
        for (int i = index; i < A.size(); i ++) {
            if (i > index && A.get(i).equals(A.get(i - 1))) {
                continue;
            }
            int val = A.get(i);
            current.add(val);
            result.add(new ArrayList<>(current));
            helper(result, current, A, i + 1);
            current.remove(current.size() - 1);
        }
    }
}