combinations

gistfile1.txt

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

/*
시간/공간 복잡도 : O(nCk) nCk = (n!/k!(n-k)!)? 시간 복잡도 계산이 은근히 복잡하다.
n회 루프 중 현재 원소의 갯수 n이 < k 일때까지 계속해서 재귀호출을 하므로..으

순열/조합 을 한번에 짜는게 의외로 잘 안된다. 이번에도 대여섯번 컴파일러에 의존해서 버그 수정 후 accepted. 연습이 필요할 듯
*/

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> combi;
        
        if(n == 0 || n < k) return res;
        combination(combi, 1, n, k, &res);
        
        return res;
    }
    
    void combination(vector<int> combi, int index, int n, int k, vector<vector<int>>* res) {
        for(int i=index; i <= n ; i++) {
            combi.push_back(i);
            
            if(combi.size() == k) {
                res->push_back(combi);
            } else {
                combination(combi, i+1, n, k, res);
            }
            
            combi.pop_back();
        }
    }
};