문제 개요
숫자로 이루어진 목록 nums와 정수 k가 주어졌을 때, nums를 각 부분집합의 원소 합이 모두 동일해지도록 k개의 서로 다른 부분집합으로 나눌 수 있는지 판별하는 프로그램을 만들어 보겠습니다.
예를 들어 입력이 nums = [4, 2, 6, 5, 1, 6, 3], k = 3이라면 결과는 참(True)입니다. 전체 합이 27이므로 각 부분집합의 합은 9가 되어야 하는데, 실제로 [6, 3], [6, 2, 1], [4, 5]처럼 분할하면 세 부분집합 모두 합이 9로 같습니다.
풀이 접근: 백트래킹(DFS)
이 문제는 대표적인 백트래킹(backtracking) 유형입니다. 각 숫자를 k개의 그룹 중 하나에 차례대로 배치해 보면서, 모든 숫자를 배치한 뒤 각 그룹의 합이 같은지 검사합니다. 도중에 유효한 분할을 찾으면 즉시 탐색을 종료하여 불필요한 연산을 줄입니다.
알고리즘 단계
- check() 함수 정의: 배열 v를 인자로 받아, v의 모든 원소가 v[0]과 같은지 확인합니다. 하나라도 다르면 false를, 모두 같으면 true를 반환합니다.
- dfs() 함수 정의: 현재 인덱스 idx, 배열 nums, 각 그룹의 합을 저장하는 배열 temp를 인자로 받습니다.
- idx가 nums의 크기와 같으면(모든 숫자를 배치했다면) check(temp)의 결과를 반환합니다.
- ret을 false로 초기화합니다.
- i를 0부터 temp의 크기까지 반복하며 다음을 수행합니다.
- temp[i]에 nums[idx]를 더한 뒤 dfs(idx + 1, nums, temp)를 재귀 호출합니다.
- 결과가 true이면 즉시 true를 반환합니다.
- 그렇지 않으면 temp[i]에서 nums[idx]를 빼서 원래 상태로 되돌립니다(백트래킹).
- 모든 경우를 시도했는데도 성공하지 못하면 false를 반환합니다.
- 메인 처리: 크기가 k인 배열 temp를 생성하고 dfs(0, nums, temp)의 결과를 반환합니다.
C++ 구현 예제
다음 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool check(vector<int>& v) {
for (int i = 1; i < v.size(); i++) {
if (v[i] != v[0])
return false;
}
return true;
}
bool dfs(int idx, vector<int>& nums, vector<int>& temp) {
if (idx == nums.size()) {
return check(temp);
}
bool ret = false;
for (int i = 0; i < temp.size(); i++) {
temp[i] += nums[idx];
ret = dfs(idx + 1, nums, temp);
if (ret)
return true;
temp[i] -= nums[idx];
}
return false;
}
bool solve(vector<int>& nums, int k) {
vector<int> temp(k);
return dfs(0, nums, temp);
}
};
bool solve(vector<int>& nums, int k) {
return (new Solution())->solve(nums, k);
}
int main(){
vector<int> v = {4, 2, 6, 5, 1, 6, 3};
int k = 3;
cout << solve(v, 3);
}
입력
{4, 2, 6, 5, 1, 6, 3}, 3
출력
1
시간 복잡도
각 숫자마다 최대 k개의 그룹을 선택할 수 있으므로, 최악의 경우 시간 복잡도는 O(kn)입니다(n은 nums의 길이). 실전에서는 가지치기(pruning)를 추가하면 탐색 공간을 크게 줄일 수 있습니다. 예를 들어 전체 합이 k로 나누어떨어지지 않으면 바로 false를 반환하거나, 특정 그룹의 합이 목표 합(전체 합 ÷ k)을 초과하면 해당 분기를 조기에 포기하는 방식이 효과적입니다.