```
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(n <= 0 || k <= 0 || n < k)
return result;
//Initialize the array nums.
//Not really required.
//nums is just used to explain the concept better when a generic array of say strings are used
//index i stores the value i+1
int[] nums = new int[n];
for(int i = 0; i < n; i++)
nums[i] = i+1;
//This array stores the result for each combination
int[] combination = new int[k];
doCombine(nums, combination, 0, 0, n, k, result);
return result;
}
//This recursive method will loop till level = k at which point we have a combination of length k
//So we have a level variable to keep track of the level
//startIndex will indicate what the next eligible index for combination will be
//Unlike permutation, we do not have to go back to revisit the old index so, we only need to look forward
//from the startIndex position
public void doCombine(int[] nums, int[] combination, int level, int startIndex, int n, int k, List<List<Integer>>result) {
if(level == k) {
ArrayList<Integer> combinationList = new ArrayList<Integer>();
for(int i = 0; i < k; i++) {
combinationList.add(combination[i]);
}
result.add(combinationList);
return;
}
//Why do we cap the index location by n-k+level
//1 2 3 4 5 n = 5 k = 3
//For Level 0
//index 0 can have values 1 2 3
//i.e the indexes can be startIndex = 0, 1 and 2 [5-3+0]
//For Level 1, let us say the startIndex = 1 (it can not be 0 since we only look forward)
//index 1 can have values 2 3 4
//i.e the indexes can be startIndex = 1, 2 and 3 [5-3+1] so StartIndex = 1 and end index = 3
for(int i = startIndex; i <= (n-k+level); i++) { //remember to add <= for i <= (n-k+level)
combination[level] = nums[i]; // nums[i] stores i+1 in this case
doCombine(nums, combination, level+1, i+1, n, k, result);
}
}
}
```