组合问题

一、问题特点

组合问题是回溯算法的典型应用，这类问题往往会给出一个元素的集合，要求找出所有满足指定条件的子集。其核心思想就是遍历整个树，找出所有满足情况的子集，在适当条件下也可能需要进行一些剪枝操作。
其中子集的选取通常有以下几个要点：

  • 集合中是否有重复元素
  • 子集中是否有重复元素
  • 集合中任意一个元素在一个子集中是否只能出现一次（是否可以被无限次重复选取）
  • 子集需要满足哪些特殊条件（元素和为target?/元素数量为k?）

二、相关例题

（一）组合

77.组合（LeetCode）
题目要求：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。

示例：

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

解题思路：
本题从集合[1, n]中选取元素组成符合条件的子集，
原集合满足条件：

  1. 没有重复元素
  2. 按照从小到大的顺序排布
    子集需要满足条件：
  3. 子集元素个数为k
  4. 子集中元素各不相同
    为了保证不会重复取同一值，可以在递归函数中添加一个参数startIndex，及时修改取值左端，每遍历一层就将startIndex加一用于标识该索引以及该索引以前的元素已被使用，从而将剩余搜索范围缩减到[startIndex, n]

此外，通过观察发现本题搜索树可以进行适当的剪枝操作。因为需要选取k个元素组成子集，那么如果当前子集中的元素数目path.size()与剩余可以选取的元素数目(n - i + 1)的和小于k，则说明无论如何，剩余的分支不可能产生大小为k的子集，可以直接被剪除。
代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void backtracking(int n, int k, int startIndex) {
        if(path.size() == k) {
            ans.push_back(path);
            return;
        }
        // 注意通过startIndex完成的去重操作
        for(int i = startIndex; i <= n - k + path.size() - 1; ++i) {
            path.push_back(i);
            // 注意startIndex + 1中暗含的回溯操作
            backtracking(n, k, startIndex + 1);
            // 回溯，准备遍历下一个同层节点
            path.pop();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return ans;
    }
private:
    vector<int> path;
    vector<vector<int>> ans;
}

（二）组合总和

39.组合总和（LeetCode）
题目要求：

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素互不相同
1 <= target <= 40

示例：

输入：candidates = [2,3,6,7], target = 7
输出：
[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

解题思路：
本题从集合candidates中选取若干元素组成符合条件的子集，
原集合满足条件：

  1. 没有重复元素
  2. 所有元素均为正数（提示中有说明）

子集需要满足条件：

  1. 子集元素和为target
  2. 子集中元素可以相同
  3. 仅存在排序差异的子集将被视为同一子集，因此仍需要去重

由于仅存在排序差异的子集将被视为同一子集，所以需要排除类似 [7, 1, 1] 和 [1, 1, 7]这样的解，为了保证不会重复取同一值，仍可以在递归函数中添加一个参数startIndex，及时修改取值左端，每遍历一层就将startIndex加一用于标识该索引以及该索引以前的元素已被使用，从而将剩余搜索范围缩减到[startIndex, n]

此外，通过观察发现本题搜索树可以进行适当的剪枝操作。因为需要选取若干个和为k的数组成子集，当当前和超过k时说明该分支的所有路径一定不能产生元素和等于k的数组，所以可以直接剪除。
代码示例：

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
class Solution {
public:
    void backtracking(vector<int> nums, int sum, int startIndex, int target) {
        if(sum == target) {
            ans.push_back(elm);
            return;
        }else if(sum > target) {
            // 剪枝
            return;
        }
        for(int i = startIndex; i < nums.size(); ++i) {
            elm.push_back(nums[i]);
            // 注意startIndex没有累加，表明在该路径下可以重复使用本元素
            // startIndex通过for循环改变数值，保证同层的其余分支不会再次使用该元素
            backtracking(nums, sum + nums[i], i, target);
            elm.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, 0, 0, target);
        return ans;
    }
private:
    vector<int> elm;
    vector<vector<int>> ans;
};

40.组合总和II（LeetCode）
题目要求：

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。

提示：

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

示例：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

解题思路：
本题从集合candidates中选取若干元素组成符合条件的子集，
原集合满足条件：

  1. 可能有重复元素
  2. 所有元素均为正数（提示中有说明）
  3. 每一个元素仅能使用一次

子集需要满足条件：

  1. 子集元素和为target
  2. 子集中元素可以相同
  3. 仅存在排序差异的子集将被视为同一子集，因此仍需要去重

首先注意到原集合中每一个元素仅能使用一次，第一想法是使用类似于backtracking(n, k, startIndex + 1);的语句完成去重。这种方法的确可以保证原集合中每一个元素仅被取一次，但注意原集合中可能存在相同的数，此时仍有可能产生具有完全相同元素的子集（例如：candidates = [1, 2, 3, 6, 1] target = 7 那么6既可以和前面的那个1组成[1, 6]，也可以和后面的1组成[6, 1]，每个元素虽然只能取一次，但依然可以产生重复的子集）
为了解决这个问题，需要对具有相同值的元素进行树层去重（确保同一层中不使用具有相同值的元素），但不能进行树枝去重（保证值相同的元素可以同时出现在子集中）。可以设置一个元素类型为bool类型的数组visited[]存储节点是否被遍历过的信息，约定 visited[i] = true 表示该元素的值被本树枝的元素遍历过，下一次仍可使用相同值；用 visited[i] = false 表示该元素的值未被遍历或已被同层元素取过，需要剪枝。为了方便调整visited[]数组的内容，需要对candidates数组进行排序，让具有相同值的元素排在一起，确保可以在同一层去除所有重复。
代码示例：

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
31
class Solution {
public:
    void backtracking(vector<int> nums, int target, vector<bool>& visited, int sum, int startIndex) {
        if(sum == target) {
            ans.push_back(path);
            return;
        }else if(sum > target) {
            return;
        }
        for(int i = startIndex; i < nums.size(); ++i) {
            if(i > 0 && nums[i] == nums[i-1] && visited[i-1] == false) {
                // 如果相同值的元素不是在本树枝上被遍历的，说明在同一层上已被取过，不可重复取值
                continue;
            }
            visited[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, target, visited, sum + nums[i], i + 1);
            path.pop_back();
            visited[i] = false;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<bool> visited(candidates.size(), false);
        backtracking(candidates, target, visited, 0, 0);
        return ans;
    }
private:
    vector<int> path;
    vector<vector<int>> ans;
};

216.组合总和III（LeetCode）
题目要求：

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

提示：

2 <= k <= 9
1 <= n <= 60

示例：

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

解题思路：
本题从集合[1, 9]中选取若干元素组成符合条件的子集，
原集合满足条件：

  1. 所有元素均为正数（提示中有说明）
  2. 每一个元素仅能使用一次

子集需要满足条件：

  1. 子集元素和为n
  2. 子集中元素不相同
  3. 子集大小为k
  4. 仅存在排序差异的子集将被视为同一子集，因此仍需要去重

本题思路较组合总和II来说比较简单，因为原集合中没有重复元素，子集中也不能有重复元素，仍使用startIndex标记去重即可。但要注意完成对当前和值sum以及startIndex的回溯操作。又由于原集合中所有元素均为正数，所以当sum大于n时即可进行剪枝，因为该分支的结果一定无法满足条件sum = n。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void backtracking(int k, int n, int startindex, int tempsum) {
        if(tempsum > n || elm.size() > k) return;
        else if(tempsum == n && elm.size() < k) return;
        else if(tempsum == n && elm.size() == k) {
            res.push_back(elm);
            return;
        }
        for(int i = startindex; i < 10; ++i) {
            elm.push_back(i);
            backtracking(k, n, i + 1, tempsum + i);
            elm.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 1, 0);
        return res;
    }
private:
    vector<int> elm;
    vector<vector<int>> res;
};

（三）记忆化搜索优化的组合问题

组合问题也是一种典型的dfs算法，因此可以使用记忆化搜索优化时间复杂度。

474. 一和零（LeetCode）

题目要求：

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100

解题思路：
本题是一个典型的组合问题，需要从strs中选取若干元素组成符合条件的子集，
原集合满足条件：

  1. 所有元素均为二进制字符串（仅包含0和1）
  2. 每一个元素仅能使用一次

子集需要满足条件：

  1. 子集元素中的0和1的数量分别是m和n
  2. 仅存在排序差异的子集将被视为同一子集，因此仍需要去重
  3. 子集要尽可能大

题目数据量较大，因此可以使用记忆化搜索优化时间复杂度，这里使用一种新的模板，该模板更适合实现记忆化搜索。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 无记忆化搜索
class Solution {
public:
// 这是更适合dp优化的回溯算法
    int dfs(vector<string>& strs, int m, int n, int startIndex) {
        if(startIndex >= strs.size()) return 0;
        // 先检查当前字符串中包含的0和1的数量
        int ones = 0, zeros = 0;
        for(const char& c : strs[startIndex]) {
            if(c == '0') zeros++;
            else ones++;
        }
        // 尝试是否选用这个
        int ans = dfs(strs, m, n, startIndex+1);
        if(m-zeros>=0 && n-ones>=0) {
            ans = max(ans, 1+dfs(strs, m-zeros, n-ones, startIndex+1));
        }
        return ans;
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        return dfs(strs, m, n, 0);
    }
};
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:
// 这是更适合dp优化的回溯组合算法
    int dfs(vector<string>& strs, vector<vector<vector<int>>>& dp, int m, int n, int startIndex) {
        if(startIndex >= strs.size()) return 0;
        
        // 先检查当前的情况是否已经被计算过了
        if(dp[startIndex][m][n] != -1) return dp[startIndex][m][n];
        
        // 统计当前字符串中包含的0和1的数量
        int ones = 0, zeros = 0;
        for(const char& c : strs[startIndex]) {
            if(c == '0') zeros++;
            else ones++;
        }
        // 尝试是否选用这个
        int ans = dfs(strs, dp, m, n, startIndex+1);
        if(m-zeros>=0 && n-ones>=0) {
            ans = max(ans, 1+dfs(strs, dp, m-zeros, n-ones, startIndex+1));
        }
        dp[startIndex][m][n] = ans;
        return ans;
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        // -1表示没有被计算出来过
        vector<vector<vector<int>>> dp(strs.size(), vector<vector<int>>(m+1, vector<int>(n+1, -1)));
        return dfs(strs, dp, m, n, 0);
    }
};

事实上，记忆化搜索的模板可以用于任何回溯算法，只要能找到合适的dp数组，就能实现记忆化搜索。同时，本题是一个典型的01背包问题，因此可以直接使用动态规划优化。

动态规划优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        // 创建一个dp数组，dp[i][j]表示最多有i个0和j个1的子集的最大长度
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(const string& str : strs) {
            int zeros = count(str.begin(), str.end(), '0');
            int ones = str.size() - zeros;
            for(int i = m; i >= zeros; --i) {
                for(int j = n; j >= ones; --j) {
                    // 这个地方看似是二维的，但实际上是三维的，因为dp[i][j]的值依赖于dp[i-zeros][j-ones]的值
                    // 只有第一次遍历的时候，dp[i-zeros][j-ones]的值是初始值，其余时候dp[i-zeros][j-ones]都是已经计算过的值
                    dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1);
                }
            }
        }
        return dp[m][n];
    }
};