# Best solution! Beats 90% Java Iterative and recursive solution

• // The property of all combinations for k out of n is that:
// the least number of some combinations can be 1;
// the least number of some combinations can be 2;
// ...
// To sum up, the least number of every combinations cann't be greater than n-k+1;
// In fact, the ith least number of every combinations cann't be greater than n-k+i;

// My solution idea:
// All combinations for k out of n can be grouped into n-k+1 groups:
// group1: the least number of every combinations in this group is 1;
// group2: the least number of every combinations in this group is 2;
// ......
// group n-k+1: the least number of every combinations in this group is n-k+1;

// So combinations for k out of n can be solved in k grouping steps:
// Grouping Step1:
// Create group1.1 that just has number 1 as least number
// Create group1.2 that just has number 2 as least number
//....
// Create group 1.n-k+1 that just has number n-k+1 as least number
// add All groups above into result1, we will retrieve them in Step2
// Grouping Step2:
// Retrieve group1.1 from result1
// Copy group1.1 as group2.1.1 and add (group1.2_lastElement + 1) as 2th least number
// Copy group1.1 as group2.1.2 and add (group1.2_lastElement + 2) as 2th least number
//....
// Copy group1.1 as group2.1.n-k+2 and add (n-k+2) as 2th least number
// add All groups above into result2, we will retrieve them in Step3
// Retrieve group1.2 from result1
// Copy group1.2 as group2.2.1 and add (group1.2_lastElement + 1) as 2th least number
// Copy group1.2 as group2.2.2 and add (group1.2_lastElement + 2) as 2th least number
//....
// Copy group1.2 as group2.2.n-k+2 and add (n-k+2) as 2th least number
// add All groups above into result2, we will retrieve them in Step3
// Retrieve group1.3 from result ... until exhaust
// Grouping Step3: // Retrieve groups from result2 ... update them to have 3th least number
// ...
// Grouping Stepk: // Retrieve groups from result k-1 ... update them to have kth least number
// Return result k

``````//Iterative version:
public static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
//It takes k grouping steps:
for (int i = 1; i <= k; i++) {
List<List<Integer>> tmp = new ArrayList<List<Integer>>();
for (List<Integer> list : result) {
int nextElement=1;//For step 1
if(list.size()>0) nextElement=list.get(list.size() - 1)+1; //For step >1
for (;nextElement <= n - k + i; nextElement++) {
List<Integer> newList = new ArrayList<Integer>(list);
}
}
result = tmp;
}
return result;
}
//Recursive version:
public static List<List<Integer>> combineRecursive(int n, int k) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
result = combineHelper(n, k, 1, result);
return result;
}
public static List<List<Integer>> combineHelper(int n, int k, int step, List<List<Integer>> result) {
List<List<Integer>> tmp = new ArrayList<List<Integer>>();
for (List<Integer> list : result) {
int nextElement=1;//For step 1
if(list.size()>0) nextElement=list.get(list.size() - 1)+1; //For step >1
for (;nextElement <= n - k + step; nextElement++) {
List<Integer> newList = new ArrayList<Integer>(list);