回溯_leetcode.78.子集

🌸题目

🍁给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

🌸分析

🌸解法一：递归

开始假设输出子集为空，每一步都向子集添加新的整数，并生成新的子集。

public List<List<Integer>> subsets(int[] nums) {
  List<List<Integer>> output = new ArrayList();
  output.add(new ArrayList<Integer>());

  for (int num : nums) {
    List<List<Integer>> newSubsets = new ArrayList();
    for (List<Integer> curr : output) {
      newSubsets.add(new ArrayList<Integer>(curr){{add(num);}});
    }
    for (List<Integer> curr : newSubsets) {
      output.add(curr);
    }
  }
  return output;
}

🌸解法二：回溯

public static List<List<Integer>> subsets1(int[] nums) {
	 List<List<Integer>> res = new ArrayList<>();
	 dfs(0, nums, nums.length, res, new ArrayList<Integer>());
	 return res;
}
private static void dfs(int i, int[] nums, int length, List<List<Integer>> res, ArrayList<Integer> curList) {
	// TODO Auto-generated method stub
	res.add(new ArrayList<>(curList));
	for(int j = i; j < length; j++) {
		curList.add(nums[j]);
		dfs(j + 1, nums, length, res, curList);
		curList.remove(curList.size() - 1);
	}
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！