Combinations

---

Combinations: Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered,
i.e., [1,2] and [2,1] are considered to be the same combination.

---

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

---

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

---

Try this Problem on your own or check similar problems:

1. Permutations
2. Combination Sum

Solution:

Java

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        helper(n, k, 1, new ArrayList<>(), result);
        return result;
    }

    private void helper(int n, int k, int start, List<Integer> currentList, List<List<Integer>> result){
        if(currentList.size() == k){
            result.add(new ArrayList<>(currentList));
            return;
        }
        for(int i = start; i <= n; ++i){
            currentList.add(i);
            helper(n, k, i + 1, currentList, result);
            currentList.remove(currentList.size() - 1);
        }
    }
}

JavaScript

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  const result = [];
  helper(n, k, 1, [], result);
  return result;
};
function helper(n, k, start, currentList, result) {
  if (currentList.length === k) {
    result.push(currentList.slice());
    return;
  }
  for (let i = start; i <= n; ++i) {
      currentList.push(i);
      helper(n, k, i + 1, currentList, result);
      currentList.pop();
  }
}

Python

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        self.helper(n, k, 1, [], result)
        return result

    def helper(self, n: int, k: int, start: int, currentList: List[int], result: List[List[int]]) -> None:
        if len(currentList) == k:
            result.append(currentList[:])
            return
        for i in range(start, n + 1):
            currentList.append(i)
            self.helper(n, k, i + 1, currentList, result)
            currentList.pop()
            
                

C++

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        helper(n, k, 1, {}, result);
        return result;
    }
private:
     void helper(int n, int k, int start, vector<int> currentList, vector<vector<int>>& result) {
        if (currentList.size() == k) {
            result.push_back(currentList);
            return;
        }
        for (int i = start; i <= n; ++i) {
            currentList.push_back(i);
            helper(n, k, i + 1, currentList, result);
            currentList.pop_back();
        }
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n (n!/((n-k)! k!)))
• Space Complexity: O(k)

---

Explanation:

It's almost identical to the Permutations solution with only one change (you can extract this info from the problem statement too) combinations are unordered [1,2] and [2,1] are considered to be the same combination.. So the loop begins at start and for every deeper recursion call start increases (in other words it doesn’t matter if we place start at first or second position if all other picked numbers are the same). As discussed in Subsets II the complexity for generating combinations is (n!/((n-k)! * k!)) but also we have a multiplier n since we're copying the list to the result. If we omit the space complexity for the result, we only have O(k) (depth of recursion and size of the set).