Problem :

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the

frequency

of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1 :

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Example 2 :

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3 :

Input: candidates = [2], target = 1
Output: []

核心思維 :

1. 設定result儲存結果和nums為暫存
2. 對數字選項進行排列並進行深度優先搜尋

• 若目標小於0則返回
• 若目標等於0則將該組合放入結果

3. 遍歷數字選項並將數字選項放入組合，繼續深度優先搜尋並進行回溯
4. 回傳結果

程式碼 :

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //設定result儲存結果
        vector<vector<int>> result;
        //設定nums為暫存
        vector<int> nums;
        //對數字選項進行排列並進行深度優先搜尋
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0, nums, result);
        //回傳結果
        return result;
    }
    void dfs(vector<int>& candidates, int target, int index, vector<int>& nums, vector<vector<int>>& result) {
        //若目標小於0則返回
        if (target < 0)
            return;
        //若目標等於0則將該組合放入結果
        if (target == 0) {
            result.push_back(nums);
            return;
        }
        //遍歷數字選項
        for (int i=index; i<candidates.size(); i++) {
            //將數字選項放入組合
            nums.push_back(candidates[i]);
            //繼續深度優先搜尋
            dfs(candidates, target-candidates[i], i, nums, result);
            //回溯，移除最後添加的數字
            nums.pop_back();
        }
    }
};

結論 :

這題的目標是利用題目給予的數字列尋找總和為目標數值的組合數量，首先設定結果儲存的位置和暫存的位置，在數字經過排列後進行深度優先搜尋，並根據目標是否小於或等於0決定是否返回或將組合放入結果中，最後進行遍歷並繼續深度優先搜索和進行回溯，最後回傳結果。