오늘의 문제는 벡터가 주어졌을때 안에 있는 숫자들이 증가하는 모든 조합을 담은 벡터를 리턴하면 되는 문제이다. 다만, 이 문제에 까다로운 점은 nums 안에 있는 숫자들이 중복이 된 숫자들이란거고 단순한 Combination 함수를 쓰게되면 같은 조합을 두번, 세번 반복되게 담은 무수히 많은 벡터가 리턴된다는 거다. 처음에는 이 문제를 SubsetsII 같은 문제라고 생각해서 처음에 벡터를 정렬한다음에 시작할려했지만 문제가 원하는건 그게 아니였고 정렬 자체를 쓰면 안되는것이었다. 어쩔수 없이 또 다른 자료구조인 Set를 사용했고 중복되는 조합들을 막았다.
<첫번째 시도: 실패>
첫번쨰로 적은 코드이고 보기좋게 실패했다. 여기서 내가 실패한점은 curr_num이라는 맥시멈을 미리 넣고 시작했는데 애초에 nums벡터 자체가 정렬이 안된상태로 오기때문에 이런식에 접근은 좋지않았다. 그리고 dfs 가 끝나는 과정에서 내가 set를 업데이트 할려고했던것도 그리 좋은 방식이 아니었다는걸 느꼈다.
<두번째 시도: 성공>
컨테이너라는 백터를 만든다음에 curr_sum이라는 변수를 없애고 만약 dfs를 통해서 모든 요소가 pop_back() 되었을때 container.empty() 라는 if문을 넣음으로 내가 첫번째 코드에서 겪었던 어려움을 해결할수있었다. 그리고 내가 느낀거는 왠만하면은 base case 에서 어떤 과정이 이뤄저여할지를 잘 생각하는게 좋을거같다. dfs 가 리턴됐을때 뭔가를 더 할려고하면 괜히 복잡해졌다.
배운점:
1. 중복되는 요소가 있는 벡터안에서 조합을 만들때는 set를 사용하는것도 방법이다.
2. 왠만하면 base case 에서 해결하자.
