[leetcode][40] Combination Sum II 문제풀기!
👓 문제 요약
숫자들을 줄게. 그 숫자들을 조합해서 내가 원하는 숫자가 나오는 조합을 찾아줘!
단, 그 찾은 조합끼리 중복이 있으면 안돼!! 그리고 특정 숫자를 내가 준 개수보다 더 많이 쓰면 안돼!!!!
자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기
🔑 문제 풀이
모든 경우를 다 체크해서 만들어진다? 그 결과가 중복되지 않는다? 그럼 push 한다.
라는 방법이 있지만, 이 방법으로는 이미 풀어봤기 때문에 다른 방법을 찾아봤다!
그래서 제가 어떻게 풀었냐면 !!
정답에 중복이 되는 이유는 같은 숫자들끼리 아무런 구별 없이 길을 만들어 지나왔기 때문!!
같은 숫자를 쓰는 길은 한 번만 지나가게 하면 된다.!!!! 뚜둔
예를 들어
[1, 2, 2 ,2 ,5] , 5 라는 값이 주어졌다 하면,
1, 2, 5 를 지나가는 길은 오직 한 번만 체크하면 된다. 두 번째 2도 체크하고, 세 번째 2도 체크 할 필요가 없다.
🥽 소스코드 및 소스해석
var combinationSum2 = function (candidates, target) {
candidates.sort((a, b) => a - b); // 오름차순
let answer = [];
/**
* @param {number[]} candidates
* @param {number[]} path
* @param {number} start
* @param {number} target
*/
const dfs = (_candidates, path, start, _target) => {
// 다음 값도 체크해야한다!
if (_target === 0) {
answer.push(path);
return;
}
if (_target < 0 || start > _candidates.length - 1) return;
let next = start;
while (_candidates[start] === _candidates[next]) next++;
dfs(_candidates, path, next, _target);
path.push(_candidates[start]);
dfs(_candidates, [...path], start + 1, _target - _candidates[start]);
path.pop();
};
dfs(candidates, [], 0, target);
return answer;
};🔨 문제 후기
재미있다.
다른 사람의 풀이 보는 것도 재미있다. 세상에는 천재는 넘치고 내 시간은 부족하다.
Series
Algorithms
이 글은 "Algorithms" 시리즈의 23번째 기록입니다.
- 01#[프로그래머스][연습문제] 3 x N 타일링 풀이
- 02[프로그래머스][2019 kakao] 블록게임 해설
- 03[프로그래머스][2019 kakao] 길 찾기 게임 문제 해설
- 04[프로그래머스][2019 kakao] 무지의 먹방 라이브 문제 해설
- 05[프로그래머스][2019 kakao] 후보키 문제 해설
- 06[프로그래머스✈][2020 kakao] 자물쇠와 열쇠 문제 풀이
- 07[프로그래머스][2020 kakao] 기둥과 보 설치 문제 해설
- 08[프로그래머스✈][2020 kakao] 가사 검색 문제 풀이
- 09[백준🔉][16234] 인구이동 문제 해설
- 10[프로그래머스✈][2019 kakao 겨울 인턴십] 불량 사용자 문제 해설
- 11[프로그래머스✈][2020 kakao] 동굴 탐험
- 12[백준🔉][14501] 퇴사 문제 해설
- 13[프로그래머스✈][2017 카카오코드] 4단 고음 해설
- 14[프로그래머스✈][2019 kakao 겨울 인턴쉽] 징검다리 건너기 해설
- 15[프로그래머스✈][연습문제] 섬 연결하기 풀이
- 16[leetcode][15] 3sum 문제풀기!
- 17[leetcode][16] 3sum closet 문제풀기!
- 18[📣top interview question] Remove Duplicates from Sorted Array Solution 문제풀기!
- 19[📣top interview question] Best Time to Buy and Sell Stock II 문제풀기!
- 20[leetcode][30] Substring with Concatenation of All Words 문제풀기!
- 21[leetcode][31] Next Permutation 문제풀기!
- 22[leetcode][32] Longest Valid Parentheses 문제풀기
- 23[leetcode][40] Combination Sum II 문제풀기!
- 24[leetcode][42] Trapping Rain Water 문제풀기!
- 25[leetcode][43] Multiply Strings 문제풀기!
- 26[leetcode][44] Wildcard Matching 문제풀기!
- 27[leetcode][45] Jump Game II 문제풀기!