秒杀组合、排列与子集（回溯算法）

写在前

先看一下回溯算法的套路模板，参考这里。

解决一个回溯问题，实际上就是一个【决策树的遍历过程】。你需要考虑三个问题：

  1. 路径：即已经做出的选择

  2. 选择列表：即当前还可以做出的选择

  3. 结束条件：到达决策树的底层，无法再做出选择条件

回溯的框架（伪代码）

result = []
void backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return  // 避免栈溢出

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

框架的核心思想：for循环里边的递归，在递归调用之前做出选择，在递归调用之后撤销选择。

我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。

但是必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

注意：但是可以根据情况进行剪枝减小时间复杂度。

1.组合总和（39-中）

题目概述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。注意：candidates 中的数字可以无限制重复被选取！！

示例：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

思路分析：同一元素可以使用多次（start定义可选择列表的起点），所以我们进入递归不能直接进入下一个元素，而是更新状态值，直到达到底层；注：相同数字不同排列视为一个结果！如[[1], [2]]和[[2], [1]]。

保证当前已选列表（ramain）三种状态：

  • 当前路径不满足，直接返回（注意判断，remain小于0，剪枝）
  • 到达底层，且满足，记录路径
  • 路径继续搜索，进入for循环【做选择，递归（注意元素可重复选择），撤销选择】

代码：

private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> combinationSum(int[] candidates, int target){
    backTrack(candidates, new ArrayList<>(), target, 0);
    return ans;
}

private void backTrack(int[] candidates, List<Integer> list, int remain, int start) {
    // 剪枝
    if (remain < 0) return;
    else if (remain == 0) ans.add(new ArrayList<>(list));
    else {
        for (int i = start; i < candidates.length; ++i) {
            list.add(candidates[i]);
            backTrack(candidates, list, remain - candidates[i], i);
            list.remove(list.size() - 1);
        }
    }
}

2.组合（77-中）

题目概述：定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合，即相当于寻找数组[1, 2, ... n]的子数组，子数组大小为k。

注意：一个可能的结果中必须保证元素唯一性，即不能出现[1, 1]这种情况。

示例：

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

思路分析：本题使用框架可以求解。与上题不同的是：一个元素只能用一次，且k为数组的个数，但是任然可以用dfs，终止条件是k = 0。

优化思路：更新搜索起点的上界。例如：如果 n = 7, k = 4，从 5 开始搜索就已经没有意义了，这是因为：即使把 5 选上，后面的数只有 6 和 7，一共就 3 个候选数，凑不出 4 个数的组合。推导如下：

（1）搜索起点的上界 + 接下来要选择的元素个数 - 1 = n

（2）接下来要选择的元素个数 = k - list.size()

（3）搜索起点的上界：n - (k - list.size()) + 1

注意：起始位置是1，回溯的终止位置是n，都是闭区间。

代码：

private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {
    backTrack(n, new ArrayList<>(), k, 1);
    return ans;
}

private void backTrack(int n, List<Integer> list, int k, int start) {
    if (k == 0) {
        ans.add(new ArrayList<>(list));
        return;
    }

    for (int i = start; i <= n; ++i) {
        list.add(i);
        backTrack(n, list, k - 1, i + 1);
        list.remove(list.size() - 1);
    }
}

// 剪枝优化后的回溯代码
private void backTrack(int n, List<Integer> list, int k, int start) {
    if (k == list.size()) {
        ans.add(new ArrayList<>(list));
        return;
    }
    
    // 遍历搜索的起点位置（即起点上界）
    for (int i = start; i <= n - (k - list.size()) + 1; ++i) {
        list.add(i);
        backTrack(n, list, k, i + 1);
        list.remove(list.size() - 1);
    }
}

3.组合总和II（40-中）

题目概述：给定一个数组 candidates （含有重复元素！！）和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次！！

说明：

  • 所有数字（包括目标数）都是正整数。
  • 解集不能包含重复的组合。

示例：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

思路分析：与39题不同是：同一元素只用一次（start定义可选择列表的起点）但数组中含有相同元素；相同点是：相同数字列表的不同排列视为一个结果，如[[1], [2]]和[[2], [1]]。

本题关键是如何去掉结果的重复元素（由于数组中含有重复元素造成）。由于含有重复元素，我们要对数组进行排序，这很重要！去重有两种解决方案：

  • 方案1：使用Set去重，由于底层是红黑树，效率过低。

  • 方案2：通过索引确定重复元素，当前遍历索引大于起始可选列表，且元素相等（重复元素）！

代码实现：方案2

private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    // 一定要先排序！
    Arrays.sort(candidates);
    backTrack(candidates, new ArrayList<>(), target, 0);
    return new ArrayList<>(ans);
}

private void backTrack(int[] candidates, List<Integer> list, int remain, int start) {
    if (remain < 0) return;
    else if (remain == 0) {
        ans.add(new ArrayList<>(list));
        return;
    } else {
        for (int i = start; i < candidates.length; ++i) {
            // 利用索引去重
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            list.add(candidates[i]);
            backTrack(candidates, list, remain - candidates[i], i + 1);
            list.remove(list.size() - 1);
        }
    }
}

4.组合总和III（216-中）

题目概述：找出所有相加之和为 n 的 k个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。组合中元素唯一！

说明：

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例：

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

思路分析：该问题综合了前两个组合问题（重点），注意三点：

  • 子数组含有k个元素，累加和为n，所以终止条件必须满足这两条！
  • 数组元素唯一（1-9的整数），所以下一层递归的起始位置i + 1，数组内总长度为9，初始值为1，都是闭区间；
  • 剪枝优化：（1）累加和remain<0，剪枝（2）剩余元素的个数不满足使用，剪枝！

代码：

private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> combinationSum3(int k, int n) {
    int num = 9;
    backTrack(num, new ArrayList<>(), n, 1, k);
    return ans;
}

private void backTrack(int num, List<Integer> list, int remain, int start, int k) {
    if (remain < 0) return;
    else if (remain == 0 && k == list.size()) {
        ans.add(new ArrayList<>(list));
        return;
    }

    // 剩余k - list.size()需要填充
    for (int i = start; i <= num - (k - list.size()) + 1; ++i) {
        list.add(i);
        backTrack(num, list, remain - i, i + 1, k);
        list.remove(list.size() - 1);
    }
}

5.全排列（46-中）

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

示例：

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

思路分析：与组合问题不同，一般解法如方案1，全排列起始位置是0。

方案1：在搜索得到所有排列的时候，需要记录当前排列已经选了哪些元素，需要数组记录一下，出递归需要将这个元素恢复。

方案2：比较巧妙，通过以每个位置作start为起点，进递归前交换数组元素，出递归恢复数组。每次固定一个元素，当start到达数组末尾时，我们得到排列的一种组合，遍历获取即可。效率比较高！

代码：

// 方案1
private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> permute(int[] nums){
    int n = nums.length;
    boolean[] used = new boolean[n];

    backTrack(nums, new ArrayList<>(), used);
    return ans;
}
private void backTrack(int[] nums, List<Integer> path, boolean[] used) {
    if (path.size() == nums.length) {
        ans.add(new ArrayList<>(path));
        return;
    }

    // 在还未选择的数中选一个，作为排列的下一个值
    for (int i = 0; i < nums.length; ++i) {
        if (!used[i]) {
            path.add(nums[i]);
            used[i] = true;
            backTrack(nums, path, used);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

// 方案2：特别注意for循环的起始位置和起始位置的变动！
private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> permute(int[] nums){
    backTrack(nums, 0);
    return ans;
}
private void backTrack(int[] nums, int start) {
    if (start == nums.length) {
        List<Integer> list = new ArrayList<>(); 
        for (int i : nums) {
            list.add(i);
        }
        ans.add(list);
        return;
    }

    for (int i = start; i < nums.length; i++) {
        swap(nums, i, start);
        backTrack(nums, start + 1);
        swap(nums, i, start);
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

拓展(T60)：排序序列，给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

如：
输入：n = 3, k = 3
输出："213"

给定 n 和 k，返回第 k 个排列。

思路：待补充。。。

6.全排列II（47-中）

题目概述：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

思路分析：与T46实现思路相同，不同点是数组含有重复元素。关键还是如何去重！

  • 方案1：直接在加入判断是否出现过，没出现加入，效率极低。

  • 方案2：先排序（前提），然后进行剪枝，比如112， 第一个1使用然后被撤销，剪的就是这部分。所以!used（i - 1），i - 1被撤销过，且没被使用，剪枝。

  • 方案3：使用hashset保存当前要交换的位置已经有过哪些元素了，如果存在（元素相同，索引不同）直接跳过。

代码：

// 方案2
private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> permuteUnique(int[] nums){
    int n = nums.length;
    boolean[] used = new boolean[n];
    // 排序是前提
    Arrays.sort(nums);
    backTrack(nums, new ArrayList<>(), used);
    return ans;
}
private void backTrack(int[] nums, List<Integer> path, boolean[] used) {
    if (path.size() == nums.length) {
        if (!ans.contains(path)) {
            ans.add(new ArrayList<>(path));
            return;
        }
    }

    // 在还未选择的数中选一个，作为排列的下一个值
    for (int i = 0; i < nums.length; ++i) {
        if (used[i]) {
            continue;
        }
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        path.add(nums[i]);
        used[i] = true;
        backTrack(nums, path, used);
        used[i] = false;
        path.remove(path.size() - 1);
    }
}

// 方案3
private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> permuteUnique(int[] nums){
    Arrays.sort(nums);
    backTrack(nums, 0);
    return ans;
}

private void backTrack(int[] nums, int start) {
    if (start == nums.length) {
        List<Integer> list = new ArrayList<>(); 
        for (int i : nums) {
            list.add(i);
        }
        ans.add(list);
        return;
    }

    HashSet<Integer> set = new HashSet<>();
    for (int i = start; i < nums.length; i++) {
        // 具有相同值的索引不交换，直接跳过
        if (set.contains(nums[i])) continue;
        set.add(nums[i]);
        swap(nums, i, start);
        backTrack(nums, start + 1);
        swap(nums, i, start);
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

7.子集（78-中）

题目概述：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集！你可以按 任意顺序 返回解集。

示例：

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

思路分析：本题可以直接套用模板，每个元素只能使用一次!

注意：没有边界条件，直接添加到结果（任意一个都可能是子集，包括空集）。

代码：

private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> subsets(int[] nums) {
    backTrack(nums, new ArrayList<>(), 0);
    return ans;
}

private void backTrack(int[] nums, List<Integer> list, int start) {
    ans.add(new ArrayList<>(list));

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

8.子集II（90-中）

题目概述：给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。但解集不能包含重复的子集。

示例：

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

思路分析：本题与T78思路相同，但含有重复元素。关键是去重，这里采用T40的去重方法。注意：排序是去重的前提！

代码：

private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    backTrack(nums, new ArrayList<>(), 0);
    return ans;
}

private void backTrack(int[] nums, List<Integer> list, int start) {
    ans.add(new ArrayList<>(list));

    for (int i = start; i < nums.length; ++i) {
        if (i > start && nums[i] == nums[i - 1]) continue;
        list.add(nums[i]);
        backTrack(nums, list, i + 1);
        list.remove(list.size() - 1);
    }
}

总结

我们可以发现上述题目可大致分为下列几种情况：

  • 数组不含重复元素：T39组合数；T46全排列；T78子集
  • 数组中含有重复元素：T40组合数II；T47全排列II；T90子集II
  • 结果元素可重用性：不在举例说明

总结一些技巧：

  • 对于限制累加和：注意分析当前剩余值remain不同的状态，决定返回还是继续递归；
  • 对于限制子数组大小：注意在for循环优化剪枝，当剩余元素个数小于限定数组大小（剪枝），终止条件：子数组长度list.size() == 目标长度k；
  • 对于含有重复元素：关键对数组进行排序Arrays.sort()，然后优化剪枝（移动无关指针），这里还要区分[组合，子集]与[排列]去重的方法；
  • 对于全排列问题：优化方案通过交换索引swap()，遍历每个排列状态（推荐）；
  • 对于当前元素可重用：下次递归选择还是从当前位置i,否则从下一个位置i + 1开始。

ps：结果都必须保证相同数字列表的不同排列视为一个结果！

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容