9명의 난쟁이 중에서 7명의 난쟁이만 진짜임. 진짜를 찾을 수 있는 조건은 7명 키의 합이 100.
9개 중에 7개 선택하는 조합을 통해, 위 조건(7명 키의 합이 100)에 맞을 때 출력.
조합 이용시 (n,k) = (n-1,k-1) + (n-1,k) n개 중 k개 선택 = A라는 원소를 무조건 포함(그니까 k-1개 선택) + A라는 원소를 무조건 배제(배제 했으니까 k개 선택)
일단 브루트포스를 이용 1. 9명 중 7명 선택할 수 있는 케이스의 수는?
int candidates[9];
// 합이 100일 때, 모든 키를 출력해야함.
void addHeight(int sum, int nextIndex, vector<int> arr) {
if(nextIndex > 9) {
return;
}
if(arr.size() == 7 && sum == 100) {
for(int i = 0; i<7; i++) {
cout<<arr[i]<<' ';
}
cout<<endl;
return;
}
arr.push_back(candidates[nextIndex]);
addHeight(sum + candidates[nextIndex], nextIndex + 1, arr);
arr.pop_back();
addHeight(sum, nextIndex + 1, arr);
}
int main(int argc, const char * argv[]) {
for(int i = 0; i<9; i++) {
cin>>candidates[i];
}
sort(candidates, candidates + 9);
vector <int> arr;
arr.push_back(candidates[0]);
addHeight(candidates[0], 1, arr);
arr.pop_back();
addHeight(0, 1, arr);
return 0;
}
