[LeetCode] 39 - Combination Sum

문제

• 링크: https://leetcode.com/problems/combination-sum
• 난이도: Medium
• 태그: 배열, 백트래킹
• 결과: Time: 0 ms (100%), Space: 14.01 MB (73.10%)

풀이

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> v;
    
        solve(candidates, target, v, 0, res, 0);
        return res;
    }

    void solve(const vector<int>& candidates, const int target, vector<int>& cur, int sum, vector<vector<int>>& res, int idx)
    {
        if (sum > target)
        {
            return;
        }

        if (sum == target)
        {
            res.push_back(cur);
            return;
        }

        int len = candidates.size();
        for (int i = idx; i < len; ++i)
        {
            int c = candidates[i];
            cur.push_back(c);
            solve(candidates, target, cur, sum + c, res, i);
            cur.pop_back();
        }
    }
};

candidates.length의 길이 제한이 1이상 30이하로 꽤나 작다는 것에서 힌트를 얻어 ‘전부 다 해보자!’ 라는 아이디어를 생각했다. 너무 많이 더해서 target보다 커지면 돌아가는 백트래킹으로 구현했다. 문제에서는 결과 배열에 중복이 없는 것을 기대하는데, solve함수에 idx 인자를 추가하고 백트래킹을 시도하는 지점을 idx부터로 구현하면서 중복이 없도록 했다.

이 포스트는 달레 스터디(3주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.