###### tags: `LeetCode` `Medium` `DFS`
# LeetCode #77 [Combinations](https://leetcode.com/problems/combinations/)
### (Medium)
給定兩個整數 n 和 k，返回範圍 [1, n] 中所有可能的 k 個數的組合。

你可以按 任何順序 返回答案。

---
這題有兩個變數: numbers(每一個組合的大小)以及pos(現在到哪個數了)。

終止條件也有兩個: numbers歸零(到達指定長度了, 此時將暫存數組存入答案數組)以及pos>range(越界了, 通常發生在後段, 此時因為長度不滿足題目要求, 因此不將暫存數組存入答案數組, 直接返回)。

每次遞迴呼叫時傳入的numbers要-1, pos要+1(不重複整數)。

---

class Solution {
public:
    vector<vector<int>> combine(int range, int numbers) {
        vector<int> tmp;
        vector<vector<int>> ans;
        dfs(range, numbers, tmp, ans, 1);
        return ans;
    }
    void dfs(int range, int numbers, vector<int>& tmp, vector<vector<int>>& ans, int pos){
        if(numbers==0){
            ans.push_back(tmp);
            return;
        }
        else if(pos>range)return;
        for(int i=pos;i<=range;i++){
            tmp.push_back(i);
            dfs(range, numbers-1, tmp, ans, i+1);
            tmp.pop_back();
        }
    }
};