A short recursive Java solution based on C(n,k)=C(n-1,k-1)+C(n-1,k)

• Basically, this solution follows the idea of the mathematical formula C(n,k)=C(n-1,k-1)+C(n-1,k).

Here C(n,k) is divided into two situations. Situation one, number n is selected, so we only need to select k-1 from n-1 next. Situation two, number n is not selected, and the rest job is selecting k from n-1.

``````public class Solution {
public List<List<Integer>> combine(int n, int k) {
if (k == n || k == 0) {
for (int i = 1; i <= k; ++i) {
}
}
List<List<Integer>> result = this.combine(n - 1, k - 1);
return result;
}
}``````

• Could you explain what are you doing in your base condition within if?

• C(n,0) is an empty set, and C(n,n) is simply universal set {1,2,3,...,n}.

• This recursion will calculate duplicates, see C(3,2) on this image

• same idea, but iterative solution in Python:

``````def combine(self, NN, K):
result = [[[]]]
for n in range(1, NN+1):
lastRes = result[0]
for k in range(1, min(K+1, n)):
#C(n, k) = C(n-1, k) + C(n-1, k-1)
lastRes, result[k] = result[k], result[k] + [_ + [n] for _ in lastRes]
if n < K+1:
#C(n, n) = C(n-1, n-1) = 1
result.append([lastRes[0] + [n]])
return result[K]
``````

My post.

• No, the two C(3,2) are not the same. The left C(3,2) does contain the number ' 5', while the right C(3,2) does not.

• `C(3,2)` cannot contain `5` because there are only `3` items to choose from. `C(3,2)` will always be (ignoring order): `[[2, 3], [1, 3], [1, 2]]`. Two recursive paths (`5,3->4,2->3,2` and `5,3->4,3->3,2`) will reach a `combine(3,2)` call, but it's higher on the stack that 5 will be added or not.

• Correction: The left C(3,2) belongs to a combination that contain the number ' 5', while the right C(3,2) does not. So the combinations are not the same.
But yes, regarding the sub-combination itself, there are some duplicates in the recursion.

• I wrote your logic in C++

`````` vector<vector<int>> combine(int n, int k) {
vector<vector<int> > res,res1;

if(k==n || k==0)
{
vector<vector<int> > res2;
vector<int> curr;
for(int i=1;i<=k;i++)
curr.push_back(i);
res2.push_back(curr);
return res2;
}

res = combine(n-1,k-1);

for(auto itr=res.begin();itr!=res.end();itr++)
{
itr->push_back(n);
}

res1 = combine(n-1,k);

res.insert(res.end(),res1.begin(),res1.end());
return res;
}``````

• use dp to avoid computing duplicate

• ``````public List<List<Integer>> combine(int n, int k) {
if (k > n || k == 0) return new LinkedList<>();
List<List<Integer>> ans = combine(n - 1, k - 1);
return ans;
}
``````

• Thanks for your sharing, and this is my c++ code with your method.

``````class Solution {
public:
vector<vector<int>> combine(int n, int k) {
if (k == 0 || n == k) {
vector<int> combination(k);
for (int i = 1; i <= k; ++i)
combination[i - 1] = i;
return vector<vector<int>>{ combination };
}
vector<vector<int>> combinations= combine(n - 1, k - 1);
for (auto &combination : combinations)
combination.push_back(n);
auto subCombinations = combine(n - 1, k);
combinations.insert(combinations.end(), subCombinations.begin(), subCombinations.end());
return combinations;
}
};
``````

• Although no very efficient, but this idea is pretty impressive. Thanks.

• I am confused about why use Arrays.asList

• @leaptwo notice the signature:
`List<List<Integer>>`, so `return` must return a list of lists, the full explicit typed call would look like:
`return new LinkedList<List<Integer>>(Arrays.<List<Integer>>asList((List<Integer>)row));`
so `asList` is needed to create a list with a single list in it.

Actually the `new LinkedList<>()` around it is redundant, because it's already the correct type after returning from `asList`; however it is needed because the calling code mutates the result which is not allowed by `asList`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.