// Time: O(k * n * t) // Space: O(n * t) class Solution { public: /** * @param A: an integer array. * @param k: a positive integer (k <= length(A)) * @param target: a integer * @return an integer */ int kSum(vector A, int k, int target) { const int n = A.size(); // table[i][j][t] denotes the number of ways to select, // from first i elements, j elements whose sum equals to t vector>> table(2, vector>(n + 1, vector(target + 1, 0))); for (int i = 1; i <= n; ++i) { if (A[i - 1] <= target) { for (int j = i; j <= n; ++j) { table[1][j][A[i - 1]] = 1; } } } for (int i = 2; i <= k; ++i) { for (int j = i; j <= n; ++j) { for (int p = 1; p <= target; ++p) { table[i % 2][j][p] = 0; if (i < j) { table[i % 2][j][p] = table[i % 2][j - 1][p]; } if (p - A[j - 1] >= 0) { table[i % 2][j][p] += table[(i - 1) % 2][j - 1][p - A[j - 1]]; } } } } return table[k % 2][n][target]; } }; // Time: O(k * n * t) // Space: O(k * n * t) class Solution2 { public: /** * @param A: an integer array. * @param k: a positive integer (k <= length(A)) * @param target: a integer * @return an integer */ int kSum(vector A, int k, int target) { const int n = A.size(); // table[i][j][t] denotes the number of ways to select, // from first i elements, j elements whose sum equals to t vector>> table(n+1, vector>(k + 1, vector(target + 1, 0))); for (int i = 1; i <= n; ++i) { if (A[i - 1] <= target) { for (int j = i; j <= n; ++j) { table[j][1][A[i - 1]] = 1; } } } for (int i = 1; i <= n; ++i) { for (int j = min(i, k); j > 1; --j) { for (int p = 1; p <= target; ++p) { table[i][j][p] = table[i - 1][j][p]; if (p - A[i - 1] >= 0) { table[i][j][p] += table[i - 1][j - 1][p - A[i - 1]]; } } } } return table[n][k][target]; } }; // Time: O(C(n, k)) // Space: O(k) class Solution_TLE { public: /** * @param A: an integer array. * @param k: a positive integer (k <= length(A)) * @param target: a integer * @return an integer */ int kSum(vector A, int k, int target) { int ans = 0; helper(A, k, 0, target, ans); return ans; } void helper(vector A, int k, int start, int target, int & ans) { if (k < 0 || target < 0) return; if (k == 0 && target == 0) { ++ans; return; } for (int i = start; i <= A.size() - k; i++) helper(A, k - 1, i + 1, target - A[i], ans); } };

Problem