题目描述
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
解题思路
1、主要是如何剪枝？
if(i
> start
&& nums
[i
] == nums
[i
- 1]) continue;
如果数组的数nums[i]跟它前一个数nums[i - 1]相同，跳过。
代码
class Solution {
public List
<List
<Integer>> subsetsWithDup(int[] nums
) {
List
<List
<Integer>> list
= new ArrayList<>();
Arrays
.sort(nums
);
backtrack(list
, new ArrayList<>(), nums
, 0);
return list
;
}
private void backtrack(List
<List
<Integer>> list
, List
<Integer> tempList
, int[] nums
, int start
){
list
.add(new ArrayList<>(tempList
));
for(int i
= start
; i
< nums
.length
; i
++){
if(i
> start
&& nums
[i
] == nums
[i
- 1]) continue;
tempList
.add(nums
[i
]);
backtrack(list
, tempList
, nums
, i
+ 1);
tempList
.remove(tempList
.size() - 1);
}
}
}
参考：https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)
