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

39. 组合总和

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 代表当前状态下的和

``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);                }            }        }    }}``