分析

• 本题的考点：递归回溯。

• 直接暴搜即可。

代码

• C++

class Solution {
public:
    vector<vector<int>> ans;

    vector<vector<int>> combinationSum(vector<int>& c, int target) {

        vector<int> path;
        dfs(c, target, 0, path);
        return ans;
    }

    void dfs(vector<int> &c, int target, int u, vector<int> path) {
        // 每次递归path都会新创建一个，因此最后不用恢复现场
        if (target == 0) {
            ans.push_back(path);
            return;
        }
        if (u == c.size()) return;

        for (int i = 0; c[u] * i <= target; i++) {
            dfs(c, target - c[u] * i, u + 1, path);
            path.push_back(c[u]);
        }
    }
};

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;  // 区别，这种写法的效率远远高于上一种

    vector<vector<int>> combinationSum(vector<int>& c, int target) {

        dfs(c, target, 0);
        return ans;
    }

    void dfs(vector<int> &c, int target, int u) {
        // 每次递归path用的是同一个，因此需要恢复现场
        if (target == 0) {
            ans.push_back(path);
            return;
        }
        if (u == c.size()) return;

        for (int i = 0; c[u] * i <= target; i++) {  // 枚举放入c[u]的个数
            dfs(c, target - c[u] * i, u + 1);
            path.push_back(c[u]);
        }

        for (int i = 0; c[u] * i <= target; i++) path.pop_back();  // 区别，恢复现场
    }
};

• Java

class Solution {

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

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

        LinkedList<Integer> path = new LinkedList<>();
        dfs(c, target, 0, path);
        return ans;
    }

    // 当前考察到c[u], 当前方案存储在path中
    private void dfs(int[] c, int target, int u, LinkedList<Integer> path) {
        // 每次递归path用的是同一个，因此需要恢复现场
        if (target == 0) {
            ans.add((List<Integer>) path.clone());
            return;
        }
        if (u == c.length) return;

        for (int i = 0; c[u] * i <= target; i++) {  // 枚举放入c[u]的个数
            dfs(c, target - c[u] * i, u + 1, path);
            path.add(c[u]);
        }
        for (int i = 0; c[u] * i <= target; i++) path.removeLast();  // 恢复现场
    }
}

时空复杂度分析

• 时间复杂度：指数级别。

• 空间复杂度：和递归深度有关。