组合问题汇总-LeetCode 46、77、39、40、219、377、1014（回溯法，DP，贪心）
- 2019 年 12 月 13 日
- 笔记
组合问题：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
