77. Combinations

https://leetcode.com/problems/combinations/

Combinations - LeetCode

 

2개의 정수(k, n)가 주어졌을 때, 1부터 n까지의 조합에서 갯수 k를 만족하는 유일 목록을 반환하는 문제다.

n = 4, k = 2인 경우 {1,2}, {1,3}, {1,4}, {2, 3}, {2, 4}, {3, 4} 가 정답이 되겠다.

 

class Solution {
public:
    void solve(vector<int>& vec, int n, int k, int i) {
        vec.push_back(i);
        
        if (!k)
        {
            ret_.push_back(vec);
            return;
        }
                
        for (int j=i+1; j<=n; ++j)
        {
            solve(vec, n, k - 1, j);
            vec.pop_back();
        }
    }
    
    vector<vector<int>> combine(int n, int k) {
        vector<int> vec;
        vec.reserve(k);
        
        for (int i = 1; i <= n; ++i)
        {
            vec.clear();
            solve(vec, n, k-1, i);
        }
        
        return ret_;
    }
private:
    vector<vector<int>> ret_;
};