题目：给定一个含不同整数的集合，返回其所有的子集。
样例：如果 S = [1,2,3]，有如下的解：[[3],[1],[2],[1,2,3],[1,3],[1,2],[2,3],[]]
思路：因为此题求所有子集，自然想到用深度优先搜索的方法。如下树，根节点为空集，从根结点开始进行深度搜索。首先寻找到[1]，再找以[1]开头所有元素，向下找到[1,2]，再找以[1,2]开头的所有元素集合，从而找到[1,2,3]。此时已无法搜索更深层，变向上回溯。回溯到[1]结点，搜索到[1,3]。再向上回溯，直到搜索完整棵树为止。
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums.length == 0){
result.add(new ArrayList<Integer>());
return result;
}
if(nums == null){
return result;
}
Arrays.sort(nums);
helper(new ArrayList<Integer>(), nums, 0, result);
return result;
}
private void helper(ArrayList<Integer> subset, int[] nums, int startIndex,
List<List<Integer>> result){
result.add(new ArrayList<Integer>(subset));
for(int i = startIndex; i<nums.length; i++){
subset.add(nums[i]);
helper(subset, nums, i+1, result);
subset.remove(subset.size()-1);
}
}
题目：给定一个可能具有重复数字的列表，返回其所有可能的子集。
样例：如果 S = [1,2,2]，有如下的解：[[2],[1],[1,2,2],[2,2],[1,2],[]]
思路：此题的输入子集的元素可能有重复值，如果按上一题的思路，以上样例会出现两个[1,2]，为了避免第二个[1,2]的出现，在插入前做一个判断。判断当前值是否和上一个值相等（因为数列已是有序的），并且上一个值是否已经被选入，同时下标不溢出，即跳出循环，避免重复。
if(i!=0&&nums[i]==nums[i-1]&&i!=startIndex)
{
continue;
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums.length == 0){
result.add(new ArrayList<Integer>());
return result;
}
if(nums == null){
return result;
}
Arrays.sort(nums);
helper(new ArrayList<Integer>(), nums, 0, result);
return result;
}
private void helper(ArrayList<Integer> subset, int[] nums, int startIndex,
List<List<Integer>> result){
result.add(new ArrayList<Integer>(subset));
for(int i = startIndex; i<nums.length; i++){
if(i!=0&&nums[i]==nums[i-1]&&i!=startIndex)
{
continue;
}
subset.add(nums[i]);
helper(subset, nums, i+1, result);
subset.remove(subset.size()-1);
}
}