Apes Together Strong.

https://leetcode.com/problems/subsets-ii/description/ 정수 배열이 주어 질 때, 가능한 한 모든 sub set을 찾아라. 이때 중복이 없도록 하라. subset 1과 기본적으로 동일하지만, input에 중복값이 주어진다. 따라서 결과에서는 주어진 input을 제외하고 다른 중복이 있으면 안된다. 1, 22, 1 등은 허용하지 않는다.  1과 기본적으로 같은 흐름으로 하되, 결과에 중복만 set으로 filter 해 보았다.  코드더보기void subsetsWithDupBT(int idx, vector>& vRet, vector& vCur, vector& nums, unordered_set& sBuff){ string temp; for(int q = 0;..

https://leetcode.com/problems/permutations/description/ 정수 배열이 주어질 때, 가능한 모든 조합을 찾아라. 이 문제는 풀이 방법을 외우는 게 좋겠다.각 문제별로 효과적으로 푸는 체계에 대한 정리가 즉, 알고리즘 풀이법이다.  이 문제는 back tracking으로 접근해서 해결 할 수 있고, 직접 구성하기 보다는, 과정에서 오는 값으로 각 원소를 swap해 주면 원하는 결과를 얻을 수 있게 된다.  어떻게? backtrack 과정에서 현재 index와 이동하는 index를 교환한다.  코드 더보기void SwapPermute(vector& vNum, int idx1, int idx2){ if(idx1=vNum.size()) return; if(id..

https://leetcode.com/problems/combination-sum/description/ 정수 배열과 target 값이 주어 질 때, 정수 값의 합이 target이 되는 값들을 찾아라.  이전 문제보다는 종료 조건이 명확하므로, 조금 더 쉽다.  * 종료 조건 * loop의 재시작 index 지점* 다음 back track으로 넘기는 index 위 로직에 유의하면서 코드를 만든다.  코드더보기 void combiBT(int sum, vector>& vRet, vector& vCur, vector& candidates, int idx){ if(sum > combinationSum(vector& candidates, int target) { vector> vRet; vecto..

https://leetcode.com/problems/subsets/description/ 주어진 정수 배열의 모든 subset들을 출력하라. 할 때마다 감이 안잡히는 걸 보니 좋은 문제가 확실!  여러 방법이 있을 수 있겠으나, 일단 back tracking 형식으로 수를 모은다. back tracking의 주요 파라미터는 * 종료 조건 * loop의 재시작 index 지점* 다음 back track으로 넘기는 index 등이다. 따라서 위 세 값을 기본 backtrack 형식에 녹이고 잘 조절하면 답을 찾을 수 있다. 종료 조건 - 3개를 모으면 더 이상 하지 않는다.loop의 재 시작 index 지점 - 전달 받는 index 다음에서 시작한다.다음 backtrack으로 넘기는 index - 루프를 ..