组合总和

39. 组合总和

思路：
要求输出具体方案，用回溯法
每个元素可以使用多次
无重复元素，不考虑去重问题。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(0, candidates, 0, target);
        return res;
    }
    void dfs(int u, int[] a, int sum, int target) {
        if (sum >= target) {
            if (sum == target)
                res.add(new ArrayList<>(path));
            return;
        }
        for (int i = u; i < a.length; i++) {
            path.add(a[i]);
            dfs(i, a, sum + a[i], target);
            path.remove(path.size() - 1);
        }
    }
}

方法2：完全背包，再求具体方案

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] a;
    boolean[][] f;
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int n = candidates.length;
        boolean[][] f = new boolean[n + 1][target + 1];
        f[0][0] = true;
        for (int i = 1; i <= n; i++) {
            int x = candidates[i - 1];
            for (int j = 0; j <= target; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= x)
                    f[i][j] = f[i][j - x] || f[i][j];
            }
        }
        if (!f[n][target]) return res;
        this.f = f;
        this.a = candidates;
        dfs(n, target);
        return res;
    }
    void dfs(int x, int y) {
        if (y == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (x == 0) return;
        int w = a[x - 1];
        if (y >= w && f[x][y - w]) {
            path.add(w);
            dfs(x, y - w);
            path.remove(path.size() - 1);
        }
        if (f[x - 1][y]) {
            dfs(x - 1, y);
        }
    }
}

40. 组合总和 II

思路：
要求输出具体方案，用回溯法。
每个元素只能使用一次
有重复元素，需要考虑去重

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(0, candidates, 0, target);
        return res;
    }
    void dfs(int u, int[] a, int sum, int target) {
        if (sum >= target) {
            if (sum == target)
                res.add(new ArrayList<>(path));
            return;
        }
        for (int i = u; i < a.length; i++) {
            //去重
            if (i > u && a[i] == a[i - 1])
                continue;
            path.add(a[i]);
            dfs(i + 1, a, sum + a[i], target);
            path.remove(path.size() - 1);
        }
    }
}

216. 组合总和 III

思路：
要求输出具体方案，用回溯法。
选择k个数组合成目标值，结果不能有重复

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(1, k, 0, n);
        return res;
    }
    void dfs(int u, int cnt, int sum, int target) {
        if (cnt == 0) {
            if (sum == target)
                res.add(new ArrayList<>(path));
            return;
        }
        for (int i = u; i <= 9; i++) {
            path.add(i);
            dfs(i + 1, cnt - 1, sum + i, target);
            path.remove(path.size() - 1);
        }
    }
}

377. 组合总和 Ⅳ

思路：
与前三题都不一样，不是输出具体方案，而是输出方案个数，顺序不同也算不同方案(排列)，所以不是完全背包问题求方案数(组合)
状态表示：f[i]表示凑i的所有方案构成的集合
属性：方案数
状态计算：考虑当前方案的最后一个数，可以是nums中的任意一个数
f[i] += f[i - x]如果i >= x成立的话
初始化：凑0的方案有1种，什么都不选。f[0] = 1;

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] f = new int[target + 1];
        f[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int x : nums) {
                if (i >= x)
                    f[i] += f[i - x];
            }
        }
        return f[target];
    }
}