目录
leetcode.77.组合leetcode.216.组合总和 III两题差异77题代码216题代码参考leetcode.77.组合
题目链接
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例
输入: n = 4, k = 2输出:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]
leetcode.216.组合总和 III
题目链接
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
示例
example1
输入: k = 3, n = 7输出: [[1,2,4]]
example2
输入: k = 3, n = 9输出: [[1,2,6], [1,3,5], [2,3,4]]
两题差异
题一是在1至n中选取k个数的组合题二是在[1,2,3,4,5,6,7,8,9]这个集合中找到sum为n的k个数的组合,集合已经固定两题的返回都不允许重复77题代码
class Solution {List<List<Integer>> res = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public List<List<Integer>> combine(int n, int k) {if (k <= 0 || n < k){return res;}//因为是1...n,所以index从1开始backtracking(n, k, 1);return res;}private void backtracking(int n, int k, int startIndex){if (path.size() == k){res.add(new ArrayList<>(path));return;}//需要注意下方剪枝部分i <= n - (k - path.size()) + 1for (int i = startIndex; i <= n - (k - path.size()) + 1 ; i++){path.addLast(i);backtracking(n, k, i + 1);path.removeLast();}}}
216题代码
class Solution {List<List<Integer>> res = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k, n, 0, 1);return res;}//相比于77题,backtracking函数体的参数增加了sum和target;target相当于题目给的n,sum是当前的和private void backtracking(int k, int target, int sum, int startIndex){//相比77,增加sum的判断if (path.size() == k && sum == target){res.add(new ArrayList<>(path));return;}//相比77,剪枝部分有差异,同时i最大为9,不为nfor (int i = startIndex; i <= 9 && sum+i <=target ; i++){sum += i;path.addLast(i);backtracking(k, target, sum, i + 1);sum -= i;path.removeLast();}}}
参考
参考了Carl大佬c++版的77题和216题
如果觉得《【Leetcode 剑指offer刷题】回溯算法-排列组合77216》对你有帮助,请点赞、收藏,并留下你的观点哦!