> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/combinations.md).

# 77. Combinations

### Description

Given two integers *n* and *k*, return all possible combinations of *k* numbers out of 1 ... *n*.

You may return the answer in **any order**.

### Constraints

1 <= k <= n

### Approach

Backtracking

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/make-combinations-size-k)
* [Leetcode](https://leetcode.com/problems/combinations)
* ProgramCreek
* YouTube

### Examples

{% tabs %}
{% tab title="Example 1" %}
**Input:** n = 4, k = 2

**Output:** \[ \[1, 2], \[1, 3], \[1, 4], \[2, 3], \[2, 4], \[3, 4] ]
{% endtab %}

{% tab title="Example 2" %}
**Input:** n = 4, k = 2

**Output:** \[ \[1, 2, 3], \[1, 2, 4], \[1, 2, 5], \[1, 3, 4], \[1, 3, 5], \[1, 4, 5], \[2, 3, 4], \[2, 3, 5], \[2, 4, 5], \[3, 4, 5] ]
{% endtab %}
{% endtabs %}

### Solutions

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(k*kCn), where kCn = n!/((n-k)! * k!) is a number of 
 *    combinations to build. append / pop (add / removeLast) operations are 
 *    constant-time ones and the only consuming part here is to append the 
 *    built combination of length k to the output.
 * Space complexity : O(kCn) to keep all the combinations for an output.
 */

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        backtrack(resultList, new ArrayList(), 1, n, k);
        return resultList;
    }
    private void backtrack(List<List<Integer>> resultList, 
                              List<Integer> currList,
                              int start,
                              int end,
                              int k ) {
        if(k == 0) {
            resultList.add(new ArrayList(currList));
            return;
        }
        for(int i = start; i <= end-k+1; i++) {
            currList.add(i);
            backtrack(resultList, currList, i+1, end, k-1);
            currList.remove(currList.size()-1);
        }
    }
}
```

{% endtab %}
{% endtabs %}

### Follow up

* Combinations with repetitions - [GFG](https://www.geeksforgeeks.org/combinations-with-repetitions/)
* Iterative approach to print all combinations of an Array - [GFG](https://www.geeksforgeeks.org/iterative-approach-to-print-all-combinations-of-an-array/)