# LeetCode Medium 77. Combinations

tags: leetcode

問題

• Explore
• Problems

整数$n$と$k$が与えられた時, $1 \dots n$から考えられる全ての$k$個の数を返せ

解法

再帰的に解きます

• 二次元配列resと一次元配列tmpを用意します
• 再帰関数を使ってtmpに数を入れます
  • 基底はnum == kとなるときで, このときのtmpをresに入れます
  • 今までに入れた数をnumとして表現します
  • startからnまでの数字をtmpに入れ, 再帰関数を実行し, 入れた数を取り除きます
  • この時に数を取り除くことで, 一次元配列tmpを1回しか使う必要がなく, 無駄にメモリを使わなくて済みます

Python

class Solution:
    def __init__(self):
      self.res = []
  
    def combine(self, n: int, k: int) -> List[List[int]]:      
      if n < k:
        return self.res
      tmp = []
      self.helper(tmp, 1, 0, n, k)
      return self.res
    
    def helper(self, tmp, start, num, n, k):
      if num == k:
        self.res.append(tmp[:])
        return
      for i in range(start, n+1):
        tmp.append(i)
        self.helper(tmp, i+1, num+1, n, k)
        tmp.pop()

C++

class Solution {
public:
  vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    if (n < k) {
      return res;
    }
    vector<int> tmp;
    combine(res, tmp, 1, 0, n, k);
    return res;
  }
private:
  void combine(vector<vector<int>>& res, vector<int>& tmp, int start, int num, int n, int k) {
    if (num == k) {
      res.push_back(tmp);
      return;
    }
    for (int i = start; i <= n; i++) {
      tmp.push_back(i);
      combine(res, tmp, i+1, num+1, n, k);
      tmp.pop_back();
    }
  }
};
````