[LeetCode] 039 Combination Sum

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

Combination Sum - LeetCode

 

1. Backtracking 사용

 한 번 정리한 코드. 처음엔 Set을 사용했다. for문을 돌 때 현재 층(index)부터 시작하면 중복되는 경우의 수를 탐색하지 않아 Set을 사용할 필요가 없다.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        countUsed = vector<int>(candidates.size(), 0);
        
        backtraking(candidates, target, 0);
        
        return result;
    }
    
private:
    vector<int> countUsed;
    vector<vector<int>> result;
    
    void backtraking(vector<int>& nums, int target, int index)
    {
        if(target<0) return;
        else if(target==0)
        {
            vector<int> temp = vector<int>(0,0);
            for(int i=0; i<countUsed.size(); ++i)
            {
                int countSaved =0;
                while(countUsed[i] >0)
                {
                    countUsed[i]--;
                    countSaved++;
                    temp.push_back(nums[i]);
                }
                countUsed[i] = countSaved;
            }
            
            result.push_back(temp);
            return;
        }
        // 현재 층부터 시작해야 중복되는 경우의 수를 탐색하지 않는다.
        for(int i=index; i<nums.size(); ++i)
        {
            countUsed[i]++;
            backtraking(nums, target-nums[i],i);
            countUsed[i]--;
        }
    }
};

 

방문한 index를 저장하지 않고 해당 값을 바로 넣어주자.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtraking(candidates, target, 0);
        return result;
    }
    
private:
    vector<int> combi;
    vector<vector<int>> result;
    
    void backtraking(vector<int>& nums, int target, int index)
    {
        if(index == nums.size() || target<0) return;
        else if(target==0)
        {
            result.push_back(combi);
            return;
        }
        
        for(int i=index; i<nums.size(); ++i)
        {
            combi.push_back(nums[i]);
            backtraking(nums, target-nums[i],i);
            combi.pop_back();
        }
    }
};

 

2 for문을 사용하지 않고 call stack을 더 깊게 파는 방법이 있다.

첫 번째 재귀함수 호출과 두 번째 재귀함수 호출의 parameter를 주의해서 넘기자

class Solution2 {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        function(candidates,target,0);
        return result;
    }

private:
    vector<vector<int>>result;
    vector<int>current;

    void function(vector<int>& candidates,int target,int index)
    {
        if(target==0){
            result.push_back(current);
            return;
        }
        
        if(index==candidates.size() || target<0)return;
        
        current.push_back(candidates[index]);
        function(candidates,target-candidates[index],index);
        current.pop_back();
        function(candidates,target,index+1);      
    }
};