DaleStudy | Leetcode Study 3주차 - Combination Sum

Leetcode Study

문제

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]]
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
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

 

풀이

function combinationSum(candidates: number[], target: number): number[][] {
    const result: number[][] = []

    const dfs = (start: number, path: number[], sum: number) => {
        if (sum === target) {
            result.push([...path]);
            return;
        }

        if (sum > target) {
            return;
        }

        for (let i=start; i<candidates.length; i++) {
            path.push(candidates[i]);
            dfs(i, path, sum + candidates[i])
            path.pop();
        }
    }

    dfs(0, [], 0)
    return result;
};

 

이 문제는 주어진 배열의 원소들을 더해서 target 값을 만드는 모든 조합을 구하는 문제이다. 이를 해결하기 위해 DFS(깊이 우선 탐색)와 백트래킹을 활용한다. path 배열에 현재까지 선택한 원소를 저장하면서 탐색을 진행한다.
현재 합이 target과 같으면 해당 조합을 result에 추가하고, 합이 target을 초과하면 더 이상 진행하지 않고 함수를 종료한다.
이렇게 모든 경로를 탐색하며 조건을 만족하는 조합만 result에 담게 된다.

 

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