[C++] 带重复元素的K数之和计数

共计 1048 个字符，预计需要花费 3 分钟才能阅读完成。

题目

已知 n 个整数 x_1, x_2, ..., x_n，其中可能包含重复元素，以及一个整数 k(k<n)。任务是从这 n 个整数中任选 k 个整数进行相加，计算所有可能的不同和，并统计每个和出现的次数。
例如 n=3,k=2，3 个整数分别为 1,2,2。
1+2=3 1+2=3 2+2=4
总有 2 个不同的和。

输入描述

第一行，n 和 k (1 \le n \le 20, k
第二行，n 个正整数 x_1, x_2, ..., x_n (1 \le x_i \le 50)，各数之间用一个空格隔开。

输出描述

一个整数，表示不同和出现的次数。

样例

输入

3 2
1 2 2

输出

2

题解

本题比较容易 TLE，需要尽量避免耗时操作，如复制、遍历等，可以从深搜的上下文传递方面砍出来。

#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <map>
using namespace std;

vector< pair<int, int> > elements;
map<int, bool> result;

void search(int i, int r, int targetDepth){if(i < elements.size()-1) search(i+1, r, targetDepth);
    if(!targetDepth){result[r] = true;
        return;
    }
    for(int j=1;j<=elements[i].second && j<=targetDepth;j++){search(i+1, r+elements[i].first*j, targetDepth-j);
    }
}

int sum(int base, pair<int, bool> p){return base + p.second;}

int main(){ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    map<int, int> a;
    for(int i=0;i<n;i++){
        int tmp;
        cin >> tmp;
        a[tmp] += 1;
    }

    for(pair<int, int> p : a){elements.push_back(p);
    }

    search(0, 0, k);

    cout << accumulate(result.begin(), result.end(), 0, sum);

    return 0;
}