Leetcode 组合总和 与 全排列相关问题
组合总和
题目链接: Leetcode 39.组合总和
题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
样例
示例1:
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例2:
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
提示:
- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- candidate 中的每个元素都是独一无二的。
- 1 <= target <= 500
思路分析
candidates中的数字可以无限制重复被选取, 使得选出的数字之和为target, 如果只是求解集的个数, 那么这个问题就是一个完全背包问题, 但这里求解的是一个具体的方案数, 故这里不能运用完全背包的问题来分析, 看数据范围 candidates 的数据个数为30, 故这里直接暴搜dfs即可。
画出大概的深度优先遍历搜索树
C++ 代码
class Solution
{
public:
vector<vector<int>> res; // 结果
vector<int> path; // 保存每一次 dfs 的路径
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
dfs(candidates, target, 0);
return res;
}
void dfs(vector<int> &candidates, int target, int u)
{
if(!target) // 若此时target为0, 说明此时这条dfs的搜索路径可以得到一个解
{
res.push_back(path);
return ;
}
if(u == candidates.size()) return; // 此时已深搜到最后一个数字选x个的情况, 但依然不能使target减为0
int num = 0; // 记录此时的 candidates[u]选了多少个, 用于后面恢复现场
for(int k = 0; k * candidates[u] <= target; ++k) // 从选0个开始, 直到选k个的时候超过target值
{
dfs(candidates, target - k * candidates[u], u + 1);
path.push_back(candidates[u]); // 因为要实现从0个开始, 故这里这一句放这后面
++num;
}
while(num > 0) path.pop_back(), num--; // 恢复现场
}
};
组合总和II
题目链接: Leetcode 40.组合总和II
题目描述
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
样例
示例1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
思路分析
相比于组合总和这个问题加入了一个限制,即 candidates[i]只能在每个解集中使用一次, hhh从完全背包问题变为了01背包问题, 但由于是求解具体的方案数, 故这里我们还是只能dfs暴搜, 但是这次有了每个元素在每个解集中只能使用一次的条件. 故在递归搜索的过程中, 我们需要知道每一个candidates数组中的元素出现了几次, 因为此时candidates中的元素可能有重复。这里找重复元素的方法有很多, 可以开一个哈希表遍历一遍找到, 这里的写法采用的排序一遍, 这样值相等的元素都是连续的。 然后其dfs思路跟上面一题的思路基本一致。
C++ 代码
class Solution
{
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
{
sort(candidates.begin(), candidates.end()); // 排序一遍
dfs(candidates, target, 0);
return res;
}
void dfs(vector<int> &candidates, int target, int u)
{
if(!target)
{
res.push_back(path);
return;
}
if(u == candidates.size()) return;
int k = u + 1;
while(k < candidates.size() && candidates[u] == candidates[k]) ++k; //统计值为candidates[u]个数
int cnt = k - u;
int num = 0;
for(int i = 0; i <= cnt && i * candidates[u] <= target; ++i)
{
dfs(candidates, target - i * candidates[u], k);
path.push_back(candidates[u]);
++num;
}
while(num--) path.pop_back();
}
};
组合总和III
题目链接: Leetcode 216.组合总和III
题目描述
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
样例
示例1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
思路分析
相比于前面的两道问题, 这里并没有给出一个具体的数组给你一组数据, 让你从这组数据挑选组合, 这里是给你一个n, 然后在1 ~ 9中选, 每种组合中不能有重复数字, 组合中不能有重复的数字. 故同样也是直接dfs, 需要解决的问题为解决重复数字问题. 这里解决重复的方法为规定序列的顺序, 即每个解集中的数字只能是升序的。即假如一个解集为[1, 3, 5],这是个升序序列, 但[3,1,5] 由于其不是一个降序序列, 故我们不会把它作为我们的一个解集. 同时我们每次选择数字的时候应该保证之前并没有选择过,故这里需要有个标记的数组.
C++ 代码
class Solution
{
public:
vector<vector<int>> res; // 答案集合
vector<int> path; // 保存 dfs 一条路径上的数字
bool st[10]; // 标记那个数字给选过了
vector<vector<int>> combinationSum3(int k, int n)
{
memset(st, 0, sizeof st);
dfs(0, k, n, 1);
return res;
}
void dfs(int u, int k, int n, int start)
{
if(u == k) // 选择k个数
{
if(!n) res.push_back(path); // 若此时已选择了k个数, 且此时这条dfs路径上的数字之和为n,将path假如res
return;
}
for(int i = start; i <= 9; ++i) // 每次从start开始, 保证了这是一个升序
if(!st[i])
{
st[i] = true;
path.push_back(i);
dfs(u + 1, k, n - i, i + 1); // dfs的下一深度是从当前选择的 i 的下一个 i + 1开始检测
st[i] = false; // 恢复现场
path.pop_back();
}
}
};
组合总和IV
题目链接: Leetcode 377.组合总和 IV
题目描述
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
样例
示例1:
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例2:
输入：nums = [9], target = 3
输出：0
提示:
1
≤
\le
≤ nums.length
≤
\le
≤ 200
1
≤
\le
≤ nums[i]
≤
\le
≤ 1000
nums 中的所有元素 互不相同
1
≤
\le
≤ target
≤
\le
≤ 1000
思路分析
看起来像是一个完全背包问题, 但完全背包问题考虑的是一个有限的组合问题, 这里的话顺序不同的序列被视作不同的组合. 故这里并不能用背包问题的思路来考虑这个问题. 但很显然这也是一个DP问题, 同样采用闫氏DP分析法来分析
先从一维考虑, f(i)
| 集合 ： 表示的是i的所有划分方案, 即i可以由nums数组中的哪些元素的相加得到
|
|-----------状态表示--------
| |
| | 属性 : 划分方案的总数sum
|
|
|
f[i]
|
|
|
|
|-----------状态计算 : 由于这里顺序不同的序列被视作不同的组合,划分子集的原则应该不重不漏, 故这里以所有划分
方案中最后一个数是什么作为划分, 这样划分的话如 [1, 2] 和 [2, 1]是两种不同的方案.
故对于 f(i)来说, 其子集以其划分方案最后一个元素不同作为划分方案, 故所有方案划分为:
(1)划分方案最后一个元素为nums[0] (2)划分方案最后一个元素为nums[1] (3)划分方案最后一个元素为nums[2]
..... 划分方案最后一个元素为nums[k] , 由于这类方案中最后一个元素为nums[k], 故其前面的总和为 i - nums[k]
故此时找的是 i - nums[k] 最大的划分方案数, 故这类子集最大划分方案数 f[i - nums[k]],但该类子集存在
是有条件的, 即 i >= nums[k]
C++ 代码
class Solution
{
public:
unsigned f[1010];
int combinationSum4(vector<int>& nums, int target)
{
memset(f, 0, sizeof f);
f[0] = 1;
for(int i = 1; i <= target; ++i)
for(auto val : nums)
if(i >= val) f[i] += f[i - val];
return f[target];
}
};
时间复杂度 O ( n × t a r g e t ) O(n \times target) O(n×target)
全排列
题目链接: Leetcode 46.全排列
题目描述
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
样例
示例1:
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例2:
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例3:
输入：nums = [1]
输出：[[1]]
提示:
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- nums中的所有整数 互不相同
思路分析
数据量很小, 同样暴搜 dfs, 其深度优先遍历搜索树为:
全排列问题考虑的元素nums[i]应该放到那个位置上去, 从第一个位置开始选数字放, 第一个位置放了之后,再考虑第二个位置应该放什么数, 此时考虑的数字应该将第一个位置放入的数去除, 依次类推, 直到最后一个待选数字放进最后一个位置. 参考上面的搜索树理解, 这个过程需要我们恢复现场和保存那个数字是否已经被使用的信息.
C++ 代码
class Solution
{
public:
vector<vector<int>> res; // 最后的答案
vector<int> path; // 每次 dfs 的路径, 保存依次填入的数字
unordered_set<bool> hash; // 记录某个数字是否被使用
vector<vector<int>> permute(vector<int>& nums)
{
dfs(nums, 0);
return res;
}
void dfs(vector<int> &nums, int u)
{
if(u == nums.size()) // 最后一个位置已经填完, 将一条路径添加到res中
{
res.push_back(path);
return;
}
for(auto val : nums)
{
if(!hash.count(val)) // 查看val 是否已经被使用
{
hash.insert(val); // 标记为使用状态
path.push_back(val);
dfs(nums, u + 1); // 继续找下一个位置
path.pop_back(); // 恢复现场
hash.erase(val);
}
}
}
};
全排列II
题目链接: Leetcode 47.全排列II
题目描述
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
样例
示例1:
输入：nums = [1,1,2]
输出：
[[1,1,2], [1,2,1], [2,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]]
提示:
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
思路分析
相比于前面一题, 这道nums数组中包含了重复数字, 故如果继续采用上一题的写法, 那么上面样例中的示例1会出现重复的全排列, 故这里我们需要规定一下解集的规则, 例如nums[1, 1, 2] 这种序列中, 我们记第一个1为1_1, 第二个1为1_2，那么我们要求我们的解集中对这两个1的顺序有要求, 例如规定第一个1必须出现在第二个1前面, 即只能这也写 [1_1, 1_2, 2], [1_1, 2, 1_2], [2, 1_1, 1_2]。而不存在这种解集 [1_2, 1_1, 2], [1_2, 2, 1_1], [2, 1_2, 1_1] 这三种第二个1在第一个1之前的这种解集方案. 那么如何保证这个规则呢? 这里我们可以先把 nums先排序一遍, 这样重复的元素就变为了一段连续的区间.当我们继续按照我们上面的深搜思路,往第u个位置填数时, 从未被选择的数中选择时，不只是考虑它是否被选过,同时应该还注意到这个数之前的那个数是不是跟当前选择的数是否相同, 若不同证明这是一个非重复值或者是第一次选到一个重复值,可以直接放入位置中,若相同则证明这个数必定是重复数, 我们再判断前面那个位置的数是否被选过, 若选过,则本次可以继续选择这个数, 若它前面位置和它值相等的数没被选择, 则并不能保证我们上面说的那个序列规则, 此时不能选择这个数, 继续判断其他数是否可选。
C++ 代码
class Solution {
public:
vector<vector<int>> res; // 答案
vector<int> path; // 保存 dfs 每次的路径
bool st[10]; // 判断nums中第 i 个位置的数是否被选过
vector<vector<int>> permuteUnique(vector<int>& nums)
{
memset(st, 0, sizeof st);
sort(nums.begin(), nums.end()); // 先排序一遍, 保证重复值都在连续的一段区间中
dfs(nums, 0);
return res;
}
void dfs(vector<int> &nums, int u)
{
if(u == nums.size()) // 最后一个数填完了最后一个位置, 将path 加入 res 中
{
res.push_back(path);
return;
}
for(int i = 0; i < nums.size(); ++i)
{
if(!st[i]) // 首先判断nums中第i个位置的数是否被选过
{
// 接着判断若选择这个数是否满足我们说的那个序列规则, 即若这个数为重复值,则其前面与它值相同应该
// 被选择之后,这个数才能接着选, 保证重复值按照我们的序列规则,保证了不会有重复值
if(i && nums[i] == nums[i - 1] && !st[i - 1]) continue;
path.push_back(nums[i]);
st[i] = true;
dfs(nums, u + 1);
path.pop_back();
st[i] = false;
}
}
}
};