题目
题目来源leetcode
leetcode地址：78. 子集，难度：中等。
题目描述(摘自leetcode)：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1： 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2： 输入：nums = [0] 输出：[[],[0]] 提示： 1 <= nums.length <= 10 -10 <= nums[i] <= 10 nums 中的所有元素 互不相同
本地调试代码：
public static void main(String[] args) { int[] nums= new int[]{1,2,3}; System.out.println(new Solution().subsets(nums)); }
题解
NO1：回溯找节点
思路：
思路：在递归方法调用过程中使用一个begin来进行直接控制组合，整个结果集添加操作在方法一开始进行，添加新的子集在循环中进行！
代码：
class Solution { private List<List<Integer>> res; //nums = [1,2,3] =》 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] public List<List<Integer>> subsets(int[] nums) { res = new ArrayList<>(); if (nums.length == 0){ return res; } recursion(nums,0, new ArrayList<>()); return res; } /** * 回溯过程中记录节点 * @param nums * @param begin * @param pre */ public void recursion(int nums[],int begin,List<Integer> pre){ res.add(new ArrayList<>(pre)); /集合的深拷贝 for (int i = begin; i < nums.length; i++) { //begin用于间接直接控制组合 pre.add(nums[i]); recursion(nums,i + 1, pre); pre.remove(pre.size() - 1); } } }
