Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/90.html
Given an integer array nums
that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
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
-
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_better { public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); backtrack(0, nums, new ArrayList<>(), res); return res; } private void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> res) { res.add(new ArrayList<>(path)); for (int i = start; i < nums.length; i++) { if (i > start && nums[i] == nums[i-1]) { // key is i>start, so it covers input=[1,5,5] continue; } path.add(nums[i]); backtrack(i+1, nums, path, res); path.remove(path.size() - 1); } } } 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; } } } ############ class Solution { private List<List<Integer>> ans; private int[] nums; public List<List<Integer>> subsetsWithDup(int[] nums) { ans = new ArrayList<>(); Arrays.sort(nums); this.nums = nums; dfs(0, new ArrayList<>()); return ans; } private void dfs(int u, List<Integer> t) { ans.add(new ArrayList<>(t)); for (int i = u; i < nums.length; ++i) { if (i != u && nums[i] == nums[i - 1]) { continue; } t.add(nums[i]); dfs(i + 1, t); t.remove(t.size() - 1); } } }
-
// 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: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: def dfs(u, t): ans.append(t[:]) # or, t.copy() for i in range(u, len(nums)): # also good for [1,5,5], second '5' will be skipped here if # but second '5' is always covered, because i==u when ans=[1,5] and i=2 if i != u and nums[i] == nums[i - 1]: continue t.append(nums[i]) dfs(i + 1, t) t.pop() ans = [] nums.sort() dfs(0, []) return ans # iteration class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() # requirement: non-descending order res = [[]] prev_index = 0 for i in range(len(nums)): num_to_add = nums[i] newly_added_list = res.copy() start = prev_index if (i > 0 and nums[i] == nums[i - 1]) else 0 for j in range(start, len(res)): each = res[j] new_one = each.copy() # deep copy new_one.append(num_to_add) newly_added_list.append(new_one) prev_index = len(res) res = newly_added_list return res ############ 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
-
func subsetsWithDup(nums []int) [][]int { sort.Ints(nums) var ans [][]int var dfs func(u int, t []int) dfs = func(u int, t []int) { ans = append(ans, append([]int(nil), t...)) for i := u; i < len(nums); i++ { if i != u && nums[i] == nums[i-1] { continue } t = append(t, nums[i]) dfs(i+1, t) t = t[:len(t)-1] } } var t []int dfs(0, t) return ans }
-
function subsetsWithDup(nums: number[]): number[][] { nums.sort((a, b) => a - b); const n = nums.length; const t: number[] = []; const res: number[][] = []; const dfs = (i: number) => { if (i === n) { res.push([...t]); return; } t.push(nums[i]); dfs(i + 1); const num = t.pop(); while (i < n && nums[i] == num) { i++; } dfs(i); }; dfs(0); return res; }
-
impl Solution { fn dfs(mut i: usize, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>) { let n = nums.len(); if i == n { res.push(t.clone()); return; } t.push(nums[i]); Self::dfs(i + 1, t, res, nums); let num = t.pop().unwrap(); while i < n && num == nums[i] { i += 1; } Self::dfs(i, t, res, nums); } pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> { nums.sort(); let mut res = Vec::new(); Self::dfs(0, &mut Vec::new(), &mut res, &nums); res } }