【每日算法】回溯法求数组组合

力扣78.子集

题目 

给你一个整数数组 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 中的所有元素 互不相同

将题目抽象成一个树，可以看出，我们需要的是这棵树的所有节点。

回溯三部曲

• 确定递归参数

我们需要index来表示遍历的位置

 private void backTracking(int[] nums, int index) {}

• 单层搜索逻辑

因为我们要收集每一个节点，所以我们需要在每次回溯的时候，就进行节点的搜集，那么应该在哪一行进行收集呢，应该在循环的前面，因为进入循坏之后就代表着我们就需要将这次循环的数据放在数组里，进行下一次循环了

   res.add(new ArrayList<>(path));
 
        for (int i = index; i < nums.length ; i++) {
 
            path.add(nums[i]);
            backTracking(nums,i + 1);
            path.remove(path.size() - 1);
 
        }

• 搜索结束条件

当index大于数组的长度的时候，回溯就结束了

if (index >= nums.length){
            return;
        }

完整代码

class Solution {
   
    List> res = new ArrayList<>();
    List path = new ArrayList<>();
    public List> subsets(int[] nums) {
 
        backTracking(nums,0);
        return res;
    }
 
    private void backTracking(int[] nums, int index) {
        res.add(new ArrayList<>(path));
 
        if (index >= nums.length){
            return;
        }
 
        for (int i = index; i < nums.length ; i++) {
 
            path.add(nums[i]);
            backTracking(nums,i + 1);
            path.remove(path.size() - 1);
 
        }
    }
}