SubSets,SubSets2, 求数组所有子集

时间:2022-09-13 17:50:44

问题描述:

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

算法分析:第一种方法循环遍历方法,每次在原有集合基础上添加新元素。第二种算法:该类问题属于Backtraking回溯算法。

public class SubSets
{
//循环遍历法
public ArrayList<ArrayList<Integer>> subsets(int[] s)
{
if(s == null)
{
return null;
} Arrays.sort(s); ArrayList<ArrayList<Integer>> res = new ArrayList<>(); for(int i = 0; i < s.length; i ++)
{
ArrayList<ArrayList<Integer>> temp = new ArrayList<>();
//get sets that are already in result
for (ArrayList<Integer> a : res)
{
temp.add(new ArrayList<Integer>(a));
}
//add S[i] to existing sets
for (ArrayList<Integer> a : temp)
{
a.add(s[i]);
}
//add S[i] only as a set
ArrayList<Integer> single = new ArrayList<>();
single.add(s[i]);
temp.add(single); res.addAll(temp);
}
//add empty set
res.add(new ArrayList<Integer>()); return res;
} //回溯法
public List<List<Integer>> subsets_backtaking(int[] nums)
{
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
dfs(res, new ArrayList<>(), nums, 0);
return res;
}
public void dfs(List<List<Integer>> res, List<Integer> temp, int[] nums, int start)
{
res.add(new ArrayList<>(temp));
for(int i = start; i < nums.length; i ++)
{
temp.add(nums[i]);
dfs(res, temp, nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}

SubSets2:数组里有重复元素

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
public class SubSets2
{
//回溯法
public List<List<Integer>> subsets(int[] nums)
{
if(nums == null)
{
return null;
}
Arrays.sort(nums);//千万别忘了排序,否则就出错了,因为这个数组里面有重复元素
List<List<Integer>> res = new ArrayList<>();
dfs(res, new ArrayList<>(), nums, 0);
return res;
}
public void dfs(List<List<Integer>> res, List<Integer> temp, int[] nums, int start)
{
res.add(new ArrayList<>(temp));
for(int i = start; i < nums.length; i ++)
{
//skip duplicates
if(i > start && nums[i] == nums[i-1])
{
continue;
}
temp.add(nums[i]);
dfs(res, temp, nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}