# 0039. Combination Sum
###### tags: `Leetcode` `Medium` `回溯`

## 思路
蛮难想的一道题目，所以做的时候直接看答案了，用temp_list存现在的路径，ans存所有的路径，具体执行过程如图
但很明显的是如果按这个流程走下去就会有重复的结果[2,2,3][2,3,2][3,2,2], 所以这里就涉及去重，去重的办法就是按照一定的顺序找答案（3sum同理，先排序，之后拿数据的方法是第二个不小于第一个，第三个不小于第二个），本题去重的方法如下图
时间复杂度分析

## Code

class Solution {
private:
    void dfs(vector<vector<int>>& ans, vector<int>& temp_list, int index, vector<int>& candidates, int target){
        if(target == 0){
            ans.push_back(temp_list);
            return;
        }
        for(int i = index;i < candidates.size();i++){
            if(target - candidates[i] < 0){
                break;
            }
            // if(target - candidates[i] == 0){
            //     temp_list.push_back(candidates[i]);
            //     ans.push_back(temp_list);
            //     temp_list.pop_back();
            //     break;
            // }
            temp_list.push_back(candidates[i]);
            dfs(ans, temp_list, i, candidates, target-candidates[i]);
            temp_list.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        sort(candidates.begin(),candidates.end());
        vector<int> temp_list;
        dfs(ans,temp_list,0,candidates,target);
        return ans;
    }
};

第4 ~ 7行和12 ~ 17行保留一个就好了
## Result
Runtime: 4 ms, faster than **95.95%** of C++ online submissions for Combination Sum.
Memory Usage: 10.6 MB, less than **99.85%** of C++ online submissions for Combination Sum.
## Code in Java
zxh写的

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        backtrack(candidates, target, res, ans, 0);
        return ans;
    }
    public void backtrack(int[] candidates, int target, List<Integer> res, List<List<Integer>> ans, int idx){
        if(target == 0){
            List<Integer> list = new ArrayList<>(res);
            ans.add(list);
        }
        if(target<0) return;
        for(int i = idx;i < candidates.length;i++){
            if(i!=idx && candidates[i]==candidates[i-1]) continue;
            res.add(candidates[i]);
            backtrack(candidates, target-candidates[i], res, ans, i);
            res.remove(res.size()-1);
        }
    }
}

szh写的

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);
        int len = candidates.length;

        Deque<Integer> stack = new ArrayDeque<>();
        dfs(candidates, 0, len, target, stack, ans);

        return ans;
    }

    private void dfs(int[] candidates, int index, int len, int target, Deque<Integer> path, List<List<Integer>> ans){
        if (target < 0){
            return;
        }
        if (target == 0){
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < len; i++){
            if (target - candidates[i] < 0) break;
            path.addLast(candidates[i]);
            // target = target - candidates[i];
            dfs(candidates, i, len, target - candidates[i], path, ans);
            // target += path.getLast();
            path.removeLast();
        }

    }
}

## 思路
这题就有意思了，需要用到回溯，回溯又需要递归实现。
详细见以下链接，一图胜千言。
https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/

类似题目：131

## Result
执行用时：3 ms, 在所有 Java 提交中击败了77.36%的用户
内存消耗：38.5 MB, 在所有 Java 提交中击败了86.25%的用户