[leetcode] 39. 组合总和(Java)(dfs、递归、回溯)

java

39. 组合总和

直接暴力思路,用dfs+回溯枚举所有可能组合情况。难点在于每个数可取无数次。

我的枚举思路是:

外层枚举答案数组的长度,即枚举解中的数字个数,从1个开始,到target/ min(candidates)终止。

然后内层就可以dfs搜索了,

缕清状态的转换与回溯,题就做出来了。

dfs的状态函数:dfs(int k, int i, int[] candidates, List now, int nowCnt, int target, List<List> ans)

k 代表当前状态下还能拿k个数

i 代表已经搜到了数组candidates中的第i个数

now 代表当前已经拿的数的list

nowCnt 代表当前状态下的和

由此可见,当k0且nowCnttarget时,表示已经搜到一个解了,此时把解add到ans即可

class Solution {

public List<List<Integer>> combinationSum(int[] candidates, int target) {

List<List<Integer>> ans = new ArrayList<>();

if (candidates.length == 0) return new ArrayList<>();

Arrays.sort(candidates);

int maxCnt = target / candidates[0] + 1;

for (int k = 1; k < maxCnt; k++) {

dfs(k, 0, candidates, new ArrayList<>(), 0, target, ans);

}

return ans;

}

public void dfs(int k, int i, int[] candidates, List<Integer> now, int nowCnt, int target, List<List<Integer>> ans) {

if (nowCnt > target) {

return;

}

if (k == 0 && nowCnt == target) {

ans.add(new ArrayList<>(now));

return;

}

if (i >= candidates.length) return;

int num = candidates[i];

int max = target / num;

max = Math.min(max, k);

for (int j = 0; j <= max; j++) {

if (nowCnt + j * num > target) {

break;

}

for (int q = 1; q <= j; q++) {

now.add(num);

}

dfs(k - j, i + 1, candidates, now, nowCnt + j * num, target, ans);

for (int q = now.size() - 1; q >= 0; q--) {

if (now.get(q) == num) {

now.remove(q);

}

}

}

}

}

以上是 [leetcode] 39. 组合总和(Java)(dfs、递归、回溯) 的全部内容, 来源链接: www.h5w3.com/python/703313.html

回到顶部