Question

Formatted question description: https://leetcode.ca/all/90.html

90. Subsets II

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

Note:
Elements in a subset must be in non-descending order.
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],
  []
]

@tag-array

Algorithm

Take the example [1 2 2] in the title for analysis. According to the analysis in Subsets before, when the first 2 is processed, the subsets at this time are [], [1], [2], [1, 2], and when processing the second 2 at this time, if you add 2 directly after [] and [1], there will be duplication, so you can only add 2 after the last two subsets generated by the previous loop.

We use last to record the last processed number, and then determine whether the current number is the same as the above.

  • If it is different, the loop will continue from 0 to the number of the current subset.
  • If the same, then The number of new subsets minus the number of subsets in the previous loop is used as the starting point to loop, so that there will be no duplication

My solving process:

nums = [1,2,2,2]
[],1,	2,12,	2,12,22,122,	2,12,22,122,22,122,222,1222

from above, every time the new add is doubled, count: 1,2,4,8 so, the 1st half is duplicated, and 2nd half is NOT duplicated so, when going into a new loop, append duplicated num to ONLY 2nd half elements

then:

[],1

append 2, not duplicated, append as normal:

[],1,	2, 12

append 2, same as previous 2, then append last 2 elements - “2,12”

[],1,	2, 12,		22,122

append 2, same as previous 2, then append last 2 elements - “22,122”

[],1,	2, 12,		22,122,		222,1222

append 2, same as previous 2, then append last 2 elements - “222,1222”

[],1,	2, 12,		22,122,		222,1222,		2222,12222

Code

Java

  • import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Subsets_II {
    
        public static void main(String[] args) {
            Subsets_II out = new Subsets_II();
            Solution s = out.new Solution();
    
            for (List<Integer> each : s.subsetsWithDup(new int[]{1, 1})) {
                System.out.println(each.toString());
            }
        }
    
        class Solution {
            public List<List<Integer>> subsetsWithDup(int[] nums) {
                List<List<Integer>> list = new ArrayList<>();
                if (nums == null || nums.length == 0) {
                    return list;
                }
    
                Arrays.sort(nums); // requirement: non-descending order
    
                // prepare, add empty one to start looping then.
                // @note: I forgot empty
                ArrayList<Integer> empty = new ArrayList<>();
                list.add(empty);
    
                int prevIndex = 0;
    
                for (int i = 0; i < nums.length; i++) {
                    int numToAdd = nums[i];
                    List<List<Integer>> newlyAddedList = new ArrayList<>(list);
    
                    int start = (i > 0 && nums[i] == nums[i - 1]) ? prevIndex : 0;
    
                    for (int j = start; j < list.size(); j++) {
                        List<Integer> each = list.get(j);
                        ArrayList<Integer> newOne = new ArrayList<Integer>(each); // deep copy
    
                        newOne.add(numToAdd);
                        newlyAddedList.add(newOne);
    
                    }
    
                    prevIndex = list.size();
                    list = newlyAddedList;
                }
    
                return list;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/subsets-ii/
    // Time: O(2^N * N^2)
    // Space: O(2^N * N)
    class Solution {
        set<vector<int>> s;
        vector<int> tmp;
        void dfs(vector<int> &A, int i) {
            if (i == A.size()) {
                s.insert(tmp);
                return;
            }
            dfs(A, i + 1);
            tmp.push_back(A[i]);
            dfs(A, i + 1);
            tmp.pop_back();
        }
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& A) {
            sort(begin(A), end(A));
            dfs(A, 0);
            return vector<vector<int>>(begin(s), end(s));
        }
    };
    
  • class Solution(object):
      def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
    
        def dfs(start, nums, path, res, visited):
          res.append(path + [])
    
          for i in range(start, len(nums)):
            if start != i and nums[i] == nums[i - 1]:
              continue
            if i not in visited:
              visited[i] = 1
              path.append(nums[i])
              dfs(i + 1, nums, path, res, visited)
              path.pop()
              del visited[i]
    
        nums.sort()
        res = []
        visited = {}
        dfs(0, nums, [], res, visited)
        return res
    
    

All Problems

All Solutions