LeetCode 216 组合总和 III -- 回溯法-爱代码爱编程
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-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]]
思路:
其实要是做了《LeetCode 77 组合》这道题,本题其实是更加容易的。建议把这道题《LeetCode 77 组合》做一下就可以了,都是使用回溯法且做了简单的剪枝。
本题的剪枝体现在for循环中sum+i<=n
这个条件语句上。
本题Java代码:
class Solution {
int sum;
List<List<Integer>> ans = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
private void backTracking(int k, int n, int start) {
if (path.size() == k) {
if (sum == n) ans.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= 9 && sum + i <= n; i++) {
path.add(i);
sum += i;
backTracking(k, n, i + 1);
sum -= i;
path.removeLast();
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(k, n, 1);
return ans;
}
}