组合问题汇总-LeetCode 46、77、39、40、219、377、1014（回溯法，DP，贪心）
组合问题汇总-LeetCode 46、77、39、40、219、377、1014（回溯法，DP，贪心）
组合问题：LeetCode #46 77 39 40 219 377 1014
1
编程题
回溯法：
- 递归结束条件
- 变量状态的改变与恢复（tmp数组）
- 递归参数中的变量和常量，在循环中变量如何改变！！！
【LeetCode #46】全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
class Solution {
public:
vector<vector<int>> res;
void dfs(vector<int>& nums, int n, int idx){
if(idx == n){
res.push_back(nums);
return;
}
for(int i = idx; i < n; i++){
swap(nums[i], nums[idx]);
dfs(nums, n, idx+);
swap(nums[i], nums[idx]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums, nums.size(), );
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations
【LeetCode #77】组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
class Solution {
public:
vector<vector<int>> res;
vector<int> tmp;
void dfs(int n, int idx, int num){
if(idx > n+) return;
if(tmp.size() == num){
res.push_back(tmp);
return;
}
for(int i = idx; i <= n; i++){
tmp.push_back(i);
dfs(n, i+, num);
tmp.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
dfs(n, , k);
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combinations
【LeetCode #39】组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明：
所有数字（包括 target）都是正整数。 解集不能包含重复的组合。
示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ]
class Solution {
public:
vector<int> tmp;
vector<vector<int>> res;
void dfs(vector<int>& candidates, int target, int start){
if(target <= ){
if(target == ){
res.push_back(tmp);
}
return;
}
for(int i = start; i < candidates.size(); i++){
tmp.push_back(candidates[i]);
dfs(candidates, target-candidates[i], i);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, target, );
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum
【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] ]
class Solution {
public:
vector<int> tmp;
vector<vector<int>> res;
set<vector<int>> s; // 去除重复的组合
void dfs(vector<int>& candidates, int target, int start){
if(target <= ){
if(target == ){
s.insert(tmp);
}
return;
}
for(int i = start; i < candidates.size(); i++){
tmp.push_back(candidates[i]);
dfs(candidates, target-candidates[i], i+);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, target, );
for(auto i: s){
res.push_back(i);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum-ii
【LeetCode #216】组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明： 所有数字都是正整数。 解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
class Solution {
public:
vector<int> tmp;
vector<vector<int>> res;
void dfs(int k, int n, int start){
if(n <= && k == ){ // n与k都有条件限制
if(n == ){
res.push_back(tmp);
}
return;
}
for(int i = start; i < ; i++){
tmp.push_back(i);
dfs(k-1, n-i, i+);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
dfs(k, n, );
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum-iii
【LeetCode #377】组合求和 IV
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例: nums = [1, 2, 3] target = 4 输出最终为7
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
if(nums.empty()) return ;
vector<unsigned long long> dp(target+, );
dp[] = ;
for(int i = ; i <= target; i++){
for(auto j: nums){
if(i >= j){
dp[i] += dp[i-j];
}
}
}
return dp[target];
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum-iv/
【LeetCode #1014】最佳观光组合
给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。 一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例： 输入：[8,1,5,2,6] 输出：11 解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
解题思路：
虽然暴力法不能够通过，但可以给我一些贪心算法的思路！通过暴力法中tmp = A[i]+i + A[j]-j可以变换成A[i]+i的最大值与A[j]-j的最大值的求和问题，同时j > i. 因此我们可以使用一个tmp来储存max(A[i]+i), 因为其是旧数据，即i < j.
(暴力法，超时)
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& A) {
int tmp = ;
int res = INT_MIN;
for(int i = ; i < A.size(); i++){
for(int j = i+; j < A.size(); j++){
tmp = A[i] + i + A[j] - j;
res = max(res, tmp);
}
}
return res;
}
};
(贪心法)
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& A) {
int tmp = A[] + ;
int res = INT_MIN;
for(int i = ; i < A.size(); i++){
res = max(res, tmp+A[i]-i);
tmp = max(tmp, A[i]+i);
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/best-sightseeing-pair