.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
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.
Plain Text
복사
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Plain Text
복사
Example 3:
Input: candidates = [2], target = 1
Output: []
Plain Text
복사
Example 4:
Input: candidates = [1], target = 1
Output: [[1]]
Plain Text
복사
Example 5:
Input: candidates = [1], target = 2
Output: [[1,1]]
Plain Text
복사
Constraints:
•
1 <= candidates.length <= 30
•
1 <= candidates[i] <= 200
•
All elements of candidates are distinct.
•
1 <= target <= 500
My solution
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.
선택한 숫자의 합이 목표값에 해당하는 모든 고유한 후보 조합 리스트를 반환합니다. 어떤 순서로든 조합을 반환할 수 있습니다.
후보자에게서 같은 숫자를 무제한으로 선택할 수 있습니다. 선택한 숫자 중 하나 이상의 빈도가 다른 경우 두 조합이 고유합니다.
목표값까지 합한 고유 조합의 수가 지정된 입력에 대해 150개 미만임을 보장합니다.
중복가능한 모든 조합을 구하는 방법이 뭐였지?순열, 지정순열, 중복순열과 조합은 했는데, 지정 조합과 중복 조합은 해보지 않았었다.
무지성으로 DFS를 사용해 풀어보니 쉽게 풀리긴 하는데, 백트래킹? 이거 할때마다 새롭다. 제대로 사용한 거 아닌 것 같다. 그냥 배열이 모든 조합이 나오는데 겹쳐지는 배열을 유니크하게 뽑아내려고 두 배열이 동일한지를 JSON.stringify()로 감싸서 확인했다.
( 배열에 객체가 포함되어 있으면 작동하지 않을 수 있습니다. 이것이 객체에 대해 여전히 작동하는지 여부는 JSON 구현이 키를 정렬하는지 여부에 따라 다릅니다. 예를 들어 JSON은 {1:2,3:4}다음과 같을 수도 있고 같지 않을 수도 있습니다.{3:4,1:2}; 이것은 구현에 따라 다르며 사양은 어떠한 보장도 하지 않습니다.
const combinationSum = function (candidates, target) {
const res = [];
const DFS = (arr, N) => {
if (
arr.reduce((a, c) => a + c, 0) === target &&
JSON.stringify(arr) === JSON.stringify(arr.sort((a, b) => a - b))
) {
res.push(arr);
} else {
for (let i = 0; i < candidates.length; i++) {
if (N + candidates[i] <= target) {
DFS(arr.concat(candidates[i]), N + candidates[i]);
}
}
}
};
DFS([], 0);
return res;
};
JavaScript
복사
