[Algo Rhythm🕺💃] LeetCode 90. SubsetsII

📚 Problem description

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

 

Example:
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

 

🎯 Solution

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        
        backtrack(nums, new ArrayList<Integer>(), 0);
        
        return ans;
    }
    
    public void backtrack(int[] nums, List<Integer> list, int idx) { 
        ans.add(new ArrayList<Integer>(list));
        
        for(int i = idx; i < nums.length; i++) {
            if(i > idx && nums[i - 1] == nums[i]) continue;
        
            list.add(nums[i]);
            backtrack(nums, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

 

🧐 Approach

To make subset with a collection containing non-duplicates, backtracking condition is as below.

 

1. The node should not be visited.

2. The node should be on the right side of all the nodes in the list.

 

However, we now deal with collection with duplicates. Thus, we need  a extra condition : If the index of node is larger than 0, the value of node should not be same as the value of node in previous index.

To make it work, we should sort the array in advance.

 

📖  What I learned