[LeetCode] C++ 77. Combinations

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

 

문제

 

문제 분석

• 조합의 경우 순열과 다르게 순서가 달라도 같은 경우로 따지기 때문에 중복되어서 탐색하는 경우가 없게 현재 시점의 이후로만 값을 변경할 수 있도록 해야 합니다.

 

풀이

class Solution {
private:
    vector<vector<int>> result;

    void dfs(int n, vector<int>&current, int start, int k){
        if(current.size() == k){
            result.push_back(current);
            return;
        }

        for(int i = start; i <= n; ++i){
            current.push_back(i);
            dfs(n, current, i+1, k);
            current.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> current;
        dfs(n, current, 1, k);
        return result;
    }
};