leetcode —— 39. 조합 총계

중복 요소가 없는 그룹 candidates와 목표 수 target을 지정합니다. candidates에서 숫자와 target의 조합을 찾을 수 있습니다.candidates의 숫자는 무제한 반복해서 선택할 수 있습니다.
설명:

모든 숫자(target 포함)는 정수..

해집은 중복된 조합을 포함할 수 없습니다..

예 1:
입력: candidates = [2,3,6,7], target = 7, 구해집: [[7],[2,2,3]]
문제 풀이 사고방식: 귀속+거슬러 올라가서 조합이 중복되는 것을 피하기 위해 예시 1의 중복조합[2,2,3]과[3,2,2]을 사용하면 입력 candidates를 정렬한 다음에 귀속할 때temp를 현재 조합으로 설정하고 다음에temp에 넣을 수 있는 수는temp[-1]보다 크다.
Python3 코드는 다음과 같습니다.

# Python3
class Solution:
    def __init__(self):
        self.ans = []
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        def combSums(candidates,target,temp,sums):
            if target == sums:  #  
                self.ans.append(temp[:])
                return

            for n in candidates:  #  
                if sums + n > target:  #  sums target， break
                    break
                if temp and n < temp[-1]:  #  temp[-1] continue
                    continue
                temp.append(n)
                combSums(candidates,target,temp,sums+n)
                temp.pop()  #  
        candidates.sort()  #  
        combSums(candidates,target,[],0)
        return self.ans

C++ 코드는 다음과 같습니다.

# C++
class Solution {
     
private:
    vector<vector<int>> num;
    vector<int> sum;
    int i = 0;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
     
        sort(candidates.begin(),candidates.end());
        function(candidates,target,sum,i);
        return num;
    }
    void function(vector<int>& candidate, int target,vector<int> sum,int i)
    {
     
        if(target==0)
        {
     
            num.push_back(sum);
        }        
        for(;i<candidate.size();++i)  #  candidates 
        {
     
            if(candidate[i]<=target)
            {
     
                sum.push_back(candidate[i]); 
                function(candidate,target-candidate[i],sum,i);
                sum.pop_back();
            }
        }
    }
};