算法-回溯算法排列组合

回溯算法特点

回溯算法是一种暴力穷举算法
穷举的过程是遍历一颗多叉树的过程
回溯算法的框架和多叉树遍历相似

回溯算法框架

List<Value> result;
void backtrace(路径, 选择列表) {
  if (结束条件) {
    result.add(路径);
    return;
  }
  for (选择 : 选择列表) {
    做选择;
    backtrace(路径, 选择列表);
    撤销选择;

  }
}

多叉树遍历

void traverse(TreeNode root) {
  if (root == null) {
      return;
  }
  for (TreeNode child : root.children) {
      traverse(child);
  }
}

全排列问题

1，2，3，4 四个数字，给出全排列。按排列组合算法应该是4 * 3 * 2 * 1=24种。


import java.util.LinkedList;
import java.util.List;

public class BackTrace {

    static List<List<Integer>> res = new LinkedList<>();

    public static void main(String[] args) {

        permute(new int[]{1, 2, 3, 4});


        System.out.println(res);
        System.out.println(res.size());
    }

    /**
     * 主处理函数，输入一组不重复的数字，返回它们的全排列
     *
     * @param nums
     * @return
     */
    static List<List<Integer>> permute(int[] nums) {
        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();

        backtrack(nums, track);
        return res;
    }


    /**
     * 路径：记录在 track 中
     * 选择列表：nums 中不存在于 track 的那些元素  -- not contains, then do it
     * 结束条件：nums 中的元素全都在 track 中出现  -- size比对
     *
     * @param nums  选择列表
     * @param track 多叉树的路径
     */
    static void backtrack(int[] nums, LinkedList<Integer> track) {
        // 触发结束条件
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (track.contains(nums[i])) {
                continue;
            }

            // 递归前 做选择
            track.add(nums[i]);
            // 递归 进入下一层决策树
            backtrack(nums, track);
            // 递归后 取消选择
            track.removeLast();
        }
    }


}

核心是理解路径（track）、选择列表、回溯（撤销选择） 三个概念。

可视化决策树

                根节点（track=[]）
           /        |        \
          1         2         3  （第一层：选第一个数字）
        /   \     /   \     /   \
       2     3   1     3   1     2  （第二层：选第二个数字）
      /     /   /     /   /     /
     3     2   3     1   2     1  （第三层：选第三个数字）
    [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1] （结果）

基础概念

路径（track）：已经选好的数字（比如选了[1]，就是当前路径）。
选择列表：当前还能选的数字（比如nums=[1,2,3]，选了1后，选择列表剩[2,3]）。
结束条件：路径长度 = nums长度（所有数字都选完，得到一个全排列）。
回溯：选完一条分支后，撤销最后一步选择，回到上一层继续选其他分支。

以 nums = [1,2,3] 为例，理解整个过程

我们用多叉树表示决策过程，每一层代表「选第几个数字」，每个节点代表「当前路径」，分支代表「选择的数字」。

第一步：初始状态

track = []（空路径），选择列表 = [1,2,3]，进入第一层循环。

第二层：选第一个数字（3个分支）

分支1（选1）	分支2（选2）	分支3（选3）
track = [1]	track = [2]	track = [3]
选择列表 = [2,3]	选择列表 = [1,3]	选择列表 = [1,2]

第三层：以分支1（track=[1]）为例，选第二个数字

此时选择列表是[2,3]，进入第二层循环：

分支1-1（选2）	分支1-2（选3）
track = [1,2]	track = [1,3]
选择列表 = [3]	选择列表 = [2]

第四层：以分支1-1（track=[1,2]）为例，选第三个数字

此时选择列表是[3]，进入第三层循环：

选3 → track = [1,2,3]，满足「track.size()=3 == nums.length=3」，触发结束条件： → 把 [1,2,3] 加入结果集 res。
回溯：撤销最后一步选择（移除3），track 回到 [1,2]，第三层循环结束。

回溯到第三层（track=[1,2] → [1]）

分支1-1处理完，撤销选择2 → track 回到 [1]，进入下一个循环（选3）。

第三层：分支1-2（track=[1,3]）

选2 → track = [1,3,2]，满足结束条件，加入res。
回溯：移除2 → track=[1,3] → 再移除3 → track=[1]，第二层循环结束。

回溯到第一层（track=[1] → []）

撤销选择1 → track 回到空，进入下一个循环（选2），重复上述逻辑： → 得到 [2,1,3]、[2,3,1]。

再回溯到第一层（track=[]）

选3 → 得到 [3,1,2]、[3,2,1]。

关键步骤拆解（对应代码）

我们以「选1→选2→选3」为例，拆解代码执行的核心步骤：

初始调用：permute([1,2,3]) → 初始化 track=[]，调用 backtrack([1,2,3], [])。
第一层循环（i=0）：
- track 不含1 → 加入1 → track=[1]。
- 递归调用 backtrack([1,2,3], [1])（进入第二层）。
第二层循环（i=1）：
- track=[1] 不含2 → 加入2 → track=[1,2]。
- 递归调用 backtrack([1,2,3], [1,2])（进入第三层）。
第三层循环（i=2）：
- track=[1,2] 不含3 → 加入3 → track=[1,2,3]。
- 递归调用 backtrack([1,2,3], [1,2,3])。
触发结束条件：
- track.size()=3 == nums.length=3 → 把 [1,2,3] 加入res，return。
回溯（撤销选择）：
- 回到第三层 → 执行 track.removeLast() → track=[1,2]。
- 第三层循环结束 → 回到第二层 → 执行 track.removeLast() → track=[1]。
- 第二层循环下一个i（i=2）→ 选3 → 重复上述逻辑，得到[1,3,2]。
- 第二层循环结束 → 回到第一层 → 执行 track.removeLast() → track=[]。
第一层循环下一个i（i=1）：选2 → 重复逻辑，得到[2,1,3]、[2,3,1]。
第一层循环i=2：选3 → 得到[3,1,2]、[3,2,1]。

全排列总结

回溯的本质是「穷举所有分支 + 撤销选择」，通过递归遍历多叉树的所有路径。
track.contains(nums[i]) 是「剪枝」：排除已经选过的数字，避免重复。
track.removeLast() 是「回溯关键」：回到上一层，继续探索其他分支。
最终res会收集所有叶子节点的路径（即全排列）。

或者这种写法，和组合类比：

public class Test {

    static List<List<Integer>> result = new LinkedList<>();
    static LinkedList<Integer> track = new LinkedList<>();

    public static void main(String[] args) {

        int[] arr = {1,2,3,4};

        boolean[] used = new boolean[arr.length];

        backtrace(arr, used);

        result.forEach(e -> System.out.println(e));
        System.out.println(result.size());

    }

    static void backtrace(int[] arr, boolean[] used) {
        if (arr.length == track.size()) {
            result.add(new LinkedList<>(track));
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            // 元素有了 continue
            if (used[i]) {
                continue;
            }
            track.add(arr[i]);
            used[i] = true;

            backtrace(arr, used);

            track.removeLast();
            used[i] = false;
        }
    }
}

组合子集问题

1，2，3 三个数字，给出各种组合情况。按排列组合算法应该是 C3,0 + C3,1 + C3,2 + C3,3 = 1+3+3+1 = 8种


import java.util.LinkedList;
import java.util.List;

public class Subsets {

    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    LinkedList<Integer> track = new LinkedList<>();

    public static void main(String[] args) {
        List<List<Integer>> subsets = new Subsets().subsets(new int[]{1, 2, 3});
        System.out.println(subsets);
    }

    // 主函数
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0);
        return res;
    }

    // 回溯算法核心函数，遍历子集问题的回溯树
    void backtrack(int[] nums, int start) {

        // 前序位置，每个节点的值都是一个子集
        res.add(new LinkedList<>(track));

        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 做选择
            track.addLast(nums[i]);
            // 通过 start 参数控制树枝的遍历，避免产生重复的子集
            backtrack(nums, i + 1);
            // 撤销选择
            Integer integer = track.removeLast();
            System.out.println(integer);
        }
    }

}

子集对比全排列

维度	子集问题	全排列问题
选择逻辑	不回头选（选过的不再选）	全量选（只要没在路径里）
控制方式	`start` 标记下一个起点	`track.contains()` 剪枝
收集结果	所有节点（路径）	仅叶子节点
结束条件	遍历完所有数字	路径长度 = 数组长度

决策树可视化（核心）

                根节点（track=[], start=0）→ 收集：[]
           /          |          \
          1           2           3  （第一层：选第一个数字，start=0）
        /   \         |           （第二层：选第二个数字，start=1/2/3）
       2     3        3
      /               （第三层：选第三个数字，start=2/3）
     3
————————————————————————————————————
收集的子集依次是：
[] → [1] → [1,2] → [1,2,3] → [1,3] → [2] → [2,3] → [3]

关键细节解释

前序收集的意义：代码中 res.add(new LinkedList<>(track)) 放在循环前（前序位置），意味着每个节点（路径）都要收集，而不是只收集叶子节点（全排列是叶子节点）。
start的作用：强制「从当前位置往后选」，避免重复子集（比如不会出现 [2,1]，因为选2后start=2，只能选3，不能回头选1）。
回溯的本质： track.removeLast() 撤销最后一步选择，回到上一层节点，继续探索其他分支（比如选完 [1,2,3] 后，撤销3，回到 [1,2]，再撤销2，回到 [1]，探索 [1,3] 分支）。

可复选的排列组合

给出的元素可以重复选择

可复选的排列

如 [1,2] 复选可以是 [1, 1] [1, 2] [2, 1] [2, 2]

去掉 boolean[] used 控制即可

static void backtrace(int[] arr) {
    // base case 结束条件
    if (track.size() == arr.length) {
        result.add(new LinkedList<>(track));
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        track.add(arr[i]);

        backtrace(arr);

        track.removeLast();
    }
}

可复选的组合

使用 i ，而不是 i + 1 控制可复选，但复选时要注意base case 控制结束条件，避免无限制递归。

static void backtrace(int[] arr, int start) {
    // base case 结束条件，比如只选两个元素
    if (track.size() == 2) {
        result.add(new LinkedList<>(track));
        return;
    }
    for (int i = start; i < arr.length; i++) {
        track.add(arr[i]);
        // i 允许重复，i+1 不允许
        backtrace(arr, i);
        // backtrace(arr, i + 1);
        track.removeLast();
    }
}

算法