[leetcode] 90. Subsets II

문제 : https://leetcode.com/problems/subsets-ii/

---

중복이 발생할 수 있는 정수형 배열 nums가 주어질때, 만들 수 있는 부분집합들을 구하여라.

동일한 정수들로 구성된 부분집합들은 중복으로 구하지 않는다.

---

백트래킹으로 탐색하면서 부분집합을 만든다.

/*
 * nums : 입력 정수형 배열
 * ind : 탐색 중인 인덱스
 * subset : 이때까지 만든 부분집합
 * 
 * nums[ind~] 탐색하면서 subset에 정수를 추가하여 정답 부분집합을 만드는 함수 
 */
 
void backtracking(int[] nums, int ind, vector<int>& subset) {
  정답에 subset 추가.
  만약 ind 인덱스가 nums 배열 인덱스 범위를 넘어가면 함수 종료.
  
  for(int i=ind ~ num 끝) {
  	subset에 nums[i]를 추가.
  	backtracking(num, i+1, subset) // 다음 인덱스부터 다시 subset 세팅
  	subset에 nums[i]를 제거.
  }
}

전형적인 백트래킹을 적용하면 수도코드는 위와 같다.

 

이 때, 동일한 정수들로 구성된 부분집합들은 중복으로 구하지 않는다는 조건을 고민해봐야 한다.

위에서 backtracking 함수는 한 번에 추가가능한 nums 요소를 하나 추가하고 다음 인덱스부터 재귀함수를 돌린다.

nums 요소를 subset에 추가할 때 중복되는 정수는 subset에 넣지도 않고 재귀함수를 돌리지도 않으면 해결된다.

이를 위해 nums 배열을 먼저 정렬해준다.

void backtracking(int[] nums, int ind, vector<int>& subset) {
  // 생략  
  for(int i=ind ~ num 끝) {
    만약 nums[i]가 탐색중 이미 나왔다면 다음 i를 탐색한다.
    // 생략
  }
}

그리고 위와 같은 조건문을 추가하면 중복되는 부분집합을 구하지 않을 수 있다.

 

시간복잡도는 O(N^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/90.%20Subsets%20II.cpp

---

TODO 백트래킹 알고리즘 포스팅 하기.