0%

使用DFS解决数组的全排列和组合问题

本文记录了如何使用深度优先算法(DFS, Deep First Search)解决数组的全排列和组合问题。下面以4道力扣题为例,引用链接已注明在文尾。

全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例1:

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

示例2:

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

示例3:

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

本题题解请直接参见全排列 - 力扣。题解中给出的解法是没有使用标记数组的解法版本,这里给出使用标记数组used的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
vector<int> used(n);
vector<int> path;
vector<vector<int>> ans;

dfs(nums, used, 0, path, ans);
return ans;
}

void dfs(vector<int>& nums, vector<int>& used, int depth, vector<int>& path, vector<vector<int>>& ans) {
int n = nums.size();
if (depth == n) {
ans.push_back(path);
return;
}

for (int i = 0; i < n; i++) {
if (!used[i]) {
used[i] = true;
path.push_back(nums[i]);
dfs(nums, used, depth + 1, path, ans);
path.pop_back();
used[i] = false;
}
}
}
};

算法的时间复杂度为\(O(n \times n!)\)

全排列 II

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

示例1:

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

示例2:

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

本题题解请直接参见全排列 II - 力扣。本题与上题相比多了一个处理重复数的逻辑:

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
continue;
}

这个判断条件保证了对于重复数的集合,一定是从左往右逐个填入的。

首先需要注意,数组是已经排好序的,也就是说相同的数一定相邻。这里以\([1, 2_1, 2_2, 2_3]\)为例,括号里用来区别3个2。人工书写全排列的时候:

  • 填写第0个数
  • 确定第0个数为1,\([1, \_, \_, \_]\)
    • 填写第1个数
    • 确定第1个数为\(2_1\)\([1, 2_1, \_, \_]\)
      • .... (将剩下的数字遍历完毕得到\([1, 2_1, 2_2, 2_3]\),此处省略后续)
    • 重新确定第1个数,因为发现可选的数字全是2,所以停止遍历
  • 重新确定第0个数为\(2_1\)

在人工书写确定第\(j\)个数时,如果某个数是重复数,我们只会将这个数填入第\(j\)个位置一次,之后再遇到这个数就跳过它。换个角度,只有当填写第\(j\)个位置时,\(2_1\)已经填入了,填写\(2_2\)才不会产生重复(例\([1, 2_1, 2_2, \_]\), 此时\(j=3\));如果\(2_1\)还没有填入过,填写\(2_2\)就会出现重复(例\([1, 2_1, \_, \_], [1, 2_2, \_, \_]\), 此时\(j=2\))。

i > 0 && nums[i] == nums[i - 1]true就说明我们遇到了重复数, !vis[i - 1]说明上一个重复数没有填写,应该跳过:

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
continue;
}

子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

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

示例 2:

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

本题题解请参见子集 - 力扣。力扣官方给出了两种题解,分别是迭代法和递归法。

  • 迭代法会循环1 << n次(即\(2^n\)次),依据第i个二进制位判断是否将其放入子集中
  • 递归法使用变量cur来记录接下来应该选择第几个数,并依次递归这个数加入和不加入的情况

子集 II

组合总和

组合总和 II

组合

本题题目:77. 组合 - 力扣

本题题解:组合 - 题解 - 力扣。官方给出了两种方法,分别是递归方法和非递归方法。

  • 递归方法与子集中的递归方法很相似,但增加了一个限制条件k,当集合中的元素个数等于k时就停止递归。

组合 II

Reference

全排列 - 力扣

全排列 II - 力扣

子集 - 力扣

组合 - 力扣

组合总和 - 力扣