【每日算法Day 31】回溯基础1

全排列（每一位上的元素都有x种取值范围）、组合（每个元素都可以选或不选）、子集（每一位上的元素都可能存在或不存在，即0-1）问题，都可以使用回溯。解决一个回溯问题，实际上就是一个决策树的遍历过程。

在解决一个回溯问题时，我们只需要思考三个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

通常回溯算法的代码框架为：

class Solution{
    List<?> result;
    public void backrtrack(路径,选择列表){
        if(满足结束条件){
            return;
        }
        根据上一步的选择执行某些动作，例如result.add(路径);
        for(选择：选择列表){
            做下一步的选择;
            backtrack(路径,选择列表);
            撤销选择;
        }
    }
}

其核心就是框架中for循环内的递归，在递归前做选择，在递归后撤销选择。

LeetCode 78. 子集 (opens new window)

题目描述

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

示例

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

解题思路

回溯解法1：每次限定子集的大小再去回溯，只要达到限定大小就添加到结果集并返回。

public class Solution {
    List<List<Integer>> results=new ArrayList<>();
    int k=0;
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0) {
            results.add(new ArrayList<>());
            return results;
        }
        for (; k <= nums.length; k++) {
            backtrack(nums,0,new ArrayList<>());
        }
        return results;
    }

    private void backtrack(int[] nums, int start,ArrayList<Integer> path) {
        if (path.size() == k) {
            results.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums,i+1,path);
            path.remove(path.size()-1);
        }
    }
}

回溯解法2：不限定子集的大小，当要遍历的位置超过数组大小才返回。并且每一步都把当前路径（子集）添加到结果集。

class Solution {
    List<List<Integer>> results=new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0) {
            results.add(new ArrayList<>());
            return results;
        }
        backtrack(nums,0,new ArrayList<>());
        return results;
    }

    private void backtrack(int[] nums, int start,ArrayList<Integer> path) {
        if (start>nums.length) return;

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

此外和回溯算法无关，还有一种使用二进制掩码的解法，掩码的各位就代表了是否取nums[i]。

public static List<List<Integer>> binaryBit(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    //掩码i从0b1开始一直到0b11...1（共有nums.length位1）为止取值
    for (int i = 0; i < (1 << nums.length); i++) {
        List<Integer> sub = new ArrayList<Integer>();
        for (int j = 0; j < nums.length; j++)
            //如果掩码i的第j位是1则把nums[j]放到结果集中
            if (((i >> j) & 1) == 1) sub.add(nums[j]);
        res.add(sub);
    }
    return res;
}