2309-일곱난쟁이

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명 선택할 수 있는 케이스의 수는?

• 36가지.

  1. 재귀호출 이용

• nCr = n-1Cr-1 + n-1Cr

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;
}

review