LeetCode #39：Combination Sum(组合总和)

题目描述

本题是一道使用回溯法进行搜索的典型问题，从左到右搜索数组中的元素看是否能凑出 target 的值即可。注意每次进入递归要从当前元素开始向后搜索，而不是从 candidates 数组开头向后搜索，否则会重复计算组合。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        n = candidates.size();
        temp_sum = 0;
        this->target = target;

        dfs(candidates, 0);
        return res;
    }

    vector<vector<int>> res;
    vector<int> temp;
    int temp_sum;
    int n;
    int target;

    void dfs(vector<int>& candidates, int j) {
        if(temp_sum > target) { //当temp的数组和大于目标时，直接return
            return;
        } else if(temp_sum == target) { //当temp的数组和等于目标（即找到一个排列）时，将结果插入res数组
            res.push_back(temp);
            return;
        }

        for(int i = j; i < n; i ++) { //这边设置从索引j开始搜索，若从0（即从头）开始搜索会出现重复组合的情况（如2,2,3和2,3,2均将视为答案存储）
            temp.push_back(candidates[i]);
            temp_sum += candidates[i];
            dfs(candidates, i);
            temp_sum -= temp.back(); //本行和下一行即为回溯的过程，将当前的数从temp删除以便搜索新的数
            temp.pop_back();
        }
    }
};