今日算法之_154_子集
前言
Github：https://github.com/HealerJean
1、子集1
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
1.1、解题思路
类似于组合总和那样遍历
1.2、算法
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();
dsf(0, nums, res , linkedList);
return res;
}
public void dsf(int index, int[] nums,List<List<Integer>> res, LinkedList<Integer> linkedList){
res.add(new ArrayList<>(linkedList));
for (int i = index; i < nums.length; i++) {
linkedList.add(nums[i]);
dsf(i+1, nums, res , linkedList);
linkedList.removeLast();
}
}
1.3、测试
@Test
public void test(){
int[] nums = {1,2,3};
System.out.println(subsets(nums));
}
2、子集2
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。。(有顺序)
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
2.1、解题思路
类似于组合总和
2.2、算法
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();
boolean[] used = new boolean[nums.length];
dsf(0, nums, res , linkedList, used);
return res;
}
public void dsf(int index, int[] nums,List<List<Integer>> res, LinkedList<Integer> linkedList, boolean[] used){
res.add(new ArrayList<>(linkedList));
for (int i = index; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]){
continue;
}
linkedList.add(nums[i]);
used[i] = true;
dsf(i+1, nums, res , linkedList,used);
linkedList.removeLast();
used[i] = false;
}
}
2.3、测试
@Test
public void test(){
// int[] nums = {1,2,2};
int[] nums = {4,4,4,1,4};
System.out.println(subsetsWithDup(nums));
}
[[], [4], [4, 4], [4, 4, 4], [4, 4, 4, 1], [4, 4, 4, 1, 4], [4, 4, 4, 4], [4, 4, 1], [4, 4, 1, 4], [4, 4, 4], [4, 1], [4, 1, 4], [4, 4], [1], [1, 4], [4]]
3、子集3
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。。(无顺序)
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
##
3.1、解题思路
类似于组合总和
3.2、算法
3.2.1、算法1
/** */
public List<List<Integer>> subsetsWithDup(int[] nums) {
//先排序，因为上面说的是无顺序数组是不能重复的。在子集2算法中，没有排序，则是有顺序的无重复
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();
boolean[] used = new boolean[nums.length];
dsf(0, nums, res , linkedList, used);
return res;
}
public void dsf(int index, int[] nums,List<List<Integer>> res, LinkedList<Integer> linkedList, boolean[] used){
res.add(new ArrayList<>(linkedList));
for (int i = index; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]){
continue;
}
linkedList.add(nums[i]);
used[i] = true;
dsf(i+1, nums, res , linkedList,used);
linkedList.removeLast();
used[i] = false;
}
}
3.2.1、算法2
/** 解法2：注意下面的判断 */
public List<List<Integer>> subsetsWithDup2(int[] nums) {
//先排序，因为上面说的是无顺序数组是不能重复的
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();
dsf(0, nums, res , linkedList);
return res;
}
public void dsf(int index, int[] nums,List<List<Integer>> res, LinkedList<Integer> linkedList){
res.add(new ArrayList<>(linkedList));
for (int i = index; i < nums.length; i++) {
//因为已经排过序了，没有用到used数组，这里i 保证大于Index即可实现，如果这里为0的话，【[[],[1],[1,2],[2]]】
if (i > index && nums[i] == nums[i-1] ){
continue;
}
linkedList.add(nums[i]);
dsf(i+1, nums, res , linkedList);
linkedList.removeLast();
}
}
3.3、测试
@Test
public void test(){
// int[] nums = {1,2,2};
int[] nums = {4,4,4,1,4};
System.out.println(subsetsWithDup(nums));
}
[[], [1], [1, 4], [1, 4, 4], [1, 4, 4, 4], [1, 4, 4, 4, 4], [4], [4, 4], [4, 4, 4], [4, 4, 4, 4]]
