LeetCode: 39-Combination Sum 解題紀錄

Last Updated on 2022-02-17 by Clay

題目

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.

It is guaranteed 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]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

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: []

Constraints:

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• All elements of candidates are distinct.
• 1 <= target <= 500

題目給定一組不重複的數值組成的陣列（由小到大排序），以及一個正整數 target。我們要從陣列中取數值組成加總正好為 target 的新陣列（每個數值都可以重複取），並列出所有的組合並回傳。

---

解題思路

這個題目我的第一感便是使用 DFS 來解題，展開幾乎所有的變化，但是在當前組合的陣列大於 target 時不儲存直接返回。

以下直接看程式碼。

C++ 範例程式碼

class Solution {
public:
    void DFS(vector<vector<int>>& results, vector<int>& result, vector<int>& candidates, int target, int start) {
        if (target == 0) {
            results.push_back(result);
            return;
        }
                
        for (int i=start; i<candidates.size(); ++i) {
            if (candidates[i] <= target) {
                result.push_back(candidates[i]);
                DFS(results, result, candidates, target-candidates[i], i);
                result.pop_back();
            }
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // Init
        vector<int> result;
        vector<vector<int>> results;
        
        DFS(results, result, candidates, target, 0);
        
        return results;
    }
};

Python 範例程式碼

class Solution:        
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # Init
        result = []
        results = []
        
        # DFS
        def dfs(target, start):
            if target == 0: results.append(result.copy())
            elif target < 0: return
            else:
                for i in range(start, len(candidates)):
                    result.append(candidates[i])
                    dfs(target-candidates[i], i)
                    result.pop()
        
        dfs(target, 0)
        
        return results

---

References

• https://leetcode.com/problems/combination-sum/

---

• LeetCode 解題紀錄目錄