90. Subsets II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

/*

90. Subsets II
My Submissions
Question
Editorial Solution
Total Accepted: **69575** Total Submissions: **224792** Difficulty: **Medium**

Given a collection of integers that might contain duplicates, ***nums***, return all possible subsets.
**Note:** The solution set must not contain duplicate subsets.
For example,
If ***nums*** = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Hide Company Tags Facebook
Hide Tags Array Backtracking
*/
public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //https://leetcode.com/discuss/54544/very-simple-and-fast-java-solution
        /*
        The Basic idea is: use "while (i < n.length && n[i] == n[i - 1]) {i++;}" to avoid the duplicate. For example, the input is 2 2 2 3 4. Consider the helper function. The process is:

each.add(n[i]); --> add first 2 (index 0)
helper(res, new ArrayList<>(each), i + 1, n); --> go to recursion part, list each is <2 (index 0)>
while (i < n.length && n[i] == n[i - 1]) {i++;} --> after this, i == 3, add the element as in subset I
        */
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        
        helper(res, cur, 0, nums);
        return res;
        
    }
    

    public void helper(List<List<Integer>> res, List<Integer> cur, int pos, int[] n) {
        if (pos <= n.length) {
            res.add(cur);
        }
        
        int i = pos;
        while (i < n.length) {
            cur.add(n[i]);
            helper(res, new ArrayList<>(cur), i+1, n);
            cur.remove(cur.size() - 1);
            i++;
            while( i < n.length &&  n[i] == n[i-1]) {
                i++;
            }
        }
        return;
    }
}