[OJ.leetcode] combinations

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

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

/* 시간/공간 복잡도 : 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(); } } };