90.subsets-ii
/*
* @lc app=leetcode id=90 lang=java
*
* [90] Subsets II
*
* https://leetcode.com/problems/subsets-ii/description/
*
* algorithms
* Medium (56.68%)
* Likes: 9237
* Dislikes: 265
* Total Accepted: 819.4K
* Total Submissions: 1.4M
* Testcase Example: '[1,2,2]'
*
* 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
*
*
*
* 思路：使用回溯算法, 对unique数组的全排列的变种
* 问题拆分成 从n个元素的数组中选者k个元素的素全组合
* , 再收集所有子组合时去重即可
*
*/
// @lc code=start
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
for(int k = 0; k<= nums.length; k++){
dfs(nums,0,k,new ArrayList<>(),subsets);
}
return subsets;
}
public void dfs(int[] nums, int begin, int k, List<Integer> cur
, List<List<Integer>> subsets ){
if(k == cur.size()){
//donnot collect dep subset
if(isContainTargeList(subsets, new ArrayList<>(cur))){
return;
}
subsets.add(new ArrayList<>(cur));
return;
}
for(int i =begin; i <nums.length - (k - cur.size()-1); i++){
cur.add(nums[i]);
dfs(nums, i+1, k, cur, subsets);
cur.remove(cur.size()-1);
}
}
public boolean isContainTargeList(List<List<Integer>> subsets, List<Integer> targeList ){
//因为是组合，不考虑元素顺序，所有需要遍历subsets,判断是否是否包含与targeList相同的组合
for(int i = 0; i< subsets.size();i++){
Collections.sort(subsets.get(i));
Collections.sort(targeList);
if(subsets.get(i).equals(targeList)){
return true;
}
}
return false;
}
}
// @lc code=end
Comments
Post a Comment