【每日算法Day 32】回溯基础2

在状态树的遍历过程中，每个节点都表示了求解问题的不同阶段。使用深度优先遍历在回到上一层节点时需要进行状态重置，这也是回溯的含义。回溯问题中递归算法传递的参数通常称为状态变量。

LeetCode 46. 全排列 (opens new window)

题目描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例

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

解题思路

每次递归从nums中选择1个没选过的数，为此dfs方法就需要传递nums数组和boolean[] used数组来确定选择范围。终止条件是树的深度等于nums.length即0~nums.length-1位的数字都已经被选择了，使用一个栈保存dfs的路径，达到终止条件时就拷贝一份路径放到结果集中。因此参数中还需要传递path和result的引用（设为成员变量也可以）。

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result=new ArrayList<>();
    if (nums == null || nums.length == 0) return result;
    int len=nums.length;

    Deque<Integer> path=new ArrayDeque<>();
    boolean[] used=new boolean[len];
    dfs(nums,0,path,used,result);
    return result;
}

private void dfs(int[] nums,int depth,Deque<Integer> path, boolean[] used, List<List<Integer>> result) {
    if (depth == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length ; i++) {
        if (!used[i]) {
            path.offer(nums[i]);
            used[i]=true;
            dfs(nums,depth+1,path,used,result);
            path.pollLast();
            used[i]=false;
        }
    }
}

不过个人更喜欢把结果集、取值范围、判断递归终止的参考量放在类的成员变量中，让dfs传递的参数更加清晰，只传递最关键的。

public class No46_Permutations {
    List<List<Integer>> result;
    boolean[] used;
    int[] nums;

    public List<List<Integer>> permute(int[] nums) {
        result=new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        this.nums=nums;
        used=new boolean[nums.length];
        dfs(new ArrayDeque<>());
        return result;
    }

    private void dfs(Deque<Integer> path) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length ; i++) {
            if (!used[i]) {
                path.offer(nums[i]);
                used[i]=true;
                dfs(path);
                path.pollLast();
                used[i]=false;
            }
        }
    }
}

LeetCode 77. 组合 (opens new window)

题目描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解题思路

和全排列不同的是，组合中依次选择每一位的数，一旦某一位选定了原集合中的数，则下一位只会从它后面的数中选择。例如，[1,2,3,4]中选3位数字组合，选定[1,3]后下一位只能在3之后选择，因为[1,3,2]一定在前面[1,2,3]时选择过了。所以这里递归时传递的状态变量增加一个int start来确定选择数字的开始范围。递归停止的条件为已经取了k个数到路径中。

public class No77_Combinations {
    List<List<Integer>> result;
    boolean[] used;
    int n;
    int k;

    public List<List<Integer>> combine(int n, int k) {
        result=new ArrayList<>();
        if (n<=0||k<=0) return result;
        this.n=n;
        this.k=k;
        used=new boolean[n+1];
        dfs(1,new ArrayDeque<>());
        return result;
    }

    private void dfs(int start,Deque<Integer> path) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <=n; i++) {
            if (!used[i]) {
                path.offerLast(i);
                used[i]=true;
                dfs(i+1,path);
                path.pollLast();
                used[i]=false;
            }
        }
    }
}

现在回头看子集问题，和组合相比，其实就是组合问题中每一步都添加路径到结果集（而不是到了叶子节点才添加），这样就不用显式指明结束条件了。