notes/OJ notes/pages/Leetcode Combinations.md

# Leetcode Combinations

#### 2022-07-19 20:09

> ##### Algorithms:
>
> #algorithm #backtrack
>
> ##### Difficulty:
>
> #coding_problem #difficulty_medium
>
> ##### Additional tags:
>
> #leetcode #CS_list_need_understanding
>
> ##### Revisions:
>
> 2022-09-21

##### Related topics:

##### Links:

- [Link to problem](https://leetcode.com/problems/combinations/)
- [Explanation](https://leetcode.com/problems/combinations/discuss/844096/Backtracking-cheatsheet-%2B-simple-solution)

---

### Problem

Given two integers `n` and `k`, return _all possible combinations of_ `k` _numbers out of the range_ `[1, n]`.

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

#### Examples

**Example 1:**

```
**Input:** n = 4, k = 2
**Output:**
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
```

**Example 2:**

```
**Input:** n = 1, k = 1
**Output:** [[1]]
```

#### Constraints

**Constraints:**

- `1 <= n <= 20`
- `1 <= k <= n`

### Thoughts

> [!summary]
> This is a #backtrack problem

The link I mentioned on the links section already have a good
explanation on the topic.

In my eyes, backtracking means DFS-like recursion and searching in solving problems.

First, it add a option in the combinations, then backtrack it
And when it's done, it gets poped out and try another solution, and backtrack.

### Solution

Backtracking

```cpp
class Solution {
  void backtrack(vector<vector<int>> &ans, vector<int> &combs, int n, int nex,
                 int k) {
    if (k == 0) {
      ans.push_back(combs);
    } else {
      // try different solutions
      for (int i = nex; i <= n; i++) {
        combs.push_back(i);

        backtrack(ans, combs, n, i + 1, k - 1);

        combs.pop_back();
      }
    }
  }

public:
  vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans = {};
    vector<int> combs = {};

    backtrack(ans, combs, n, 1, k);

    return ans;
  }
};
```

Alternative solution using private values
```cpp
class Solution {
  vector<vector<int>> ans;
  vector<int> combs = {};
  int N, K;
  void backtrack(int cur) {
    if (combs.size() == K) {
      // we reached the end, should push to the answer array
      ans.push_back(combs);
      return;
    } else if (cur <= N) {
      combs.push_back(cur);
      backtrack(cur + 1);

      combs.pop_back();
      backtrack(cur + 1);
    }
  }

public:
  vector<vector<int>> combine(int n, int k) {
    N = n;
    K = k;
    backtrack(1);

    return ans;
  }
};
```