90.Subsets-II

90. Subsets II

题目地址

题目描述

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

代码

Approach #1 Backtracing

class Solution {
public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> array) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (array == null) return result;
​
Collections.sort(array);
​
List<Integer> list = new ArrayList<Integer>();
dfs(array, 0, list, result);
​
return result;
}
​
private void dfs(ArrayList<Integer> array, int pos, List<Integer> list, ArrayList<ArrayList<Integer>> result) {
result.add(new ArrayList<Integer>(list));
for (int i = pos; i < array.size(); i++) {
​
// exclude duplicates
if (i != pos && array.get(i) == array.get(i - 1)) {
continue;
}
​
list.add(array.get(i));
dfs(array, i + 1, list, result);
list.remove(list.size() - 1);
}
}
​
}
Last modified 2yr ago