/**

The core concept of this program is trying to list all combinations iteratively. I use a k-length array to store the number (which has the similar function as Stack). And I trace the number backwards, so the number sequence is something like the following:

e.g. n=4, k=2

[3,4]

[2,4]

[1,4]

[2,3]

[1,3]

[1,2]

the iteration will stop when the index reaches k-1, which means it has traversed all of the possibilities

*/

public class Combinations {

```
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> collection = new ArrayList<List<Integer>>();
int[] com = new int[k];
int i = k - 1;
while (i < k) {
while (i > -1 && n > i) {
com[i--] = n--;
}
if (i == -1) {
List<Integer> col = new ArrayList<Integer>();
for (int c : com)
col.add(c);
collection.add(col);
}
if (i == k - 1)
break;
n = com[++i] - 1;
}
return collection;
}
```

}