本文共 885 字,大约阅读时间需要 2 分钟。
给定一个数k和一个数n,要求从1-9中找出k个不同的数,其和为n。求出所有这样的组合。注意:每个数字在一个组合内只能被使用一次。例子:
经典的回溯。具体思路看代码。
class Solution { public List
> combinationSum3(int k, int n) { List
> res = new ArrayList<>(); // k个0-9的数最小的和为(1 + k) * k / 2 最大的和为 (19 - k) * k / 2 int minSum = (1 + k) * k / 2, maxSum = (19 - k) * k / 2; if (n < minSum || n > maxSum) return res; dfs(k, n, 1, res, new ArrayList<>()); return res; } public void dfs(int k, int n, int idx, List
> res, List list) { // 当收集到k个数时无论这k个数的和是否等于n 都会return if (k == list.size()) { if (n == 0) { res.add(new ArrayList<>(list)); } return ; } while (idx <= 9) { // 剪枝 if (n - idx < 0) break; list.add(idx); dfs(k, n - idx, idx + 1, res, list); list.remove(list.size() - 1); // 回溯 idx++; } }}
经典回溯题,掌握回溯的模板就ok
转载地址:http://iaesi.baihongyu.com/