LeetCode: 77. 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],
]

解题思路 —— 深度搜索，遍历结果

直接深度搜索，将答案搜索出来。

AC 代码

class Solution {
public:
    // 在 [start, end) 区间的整数中，找到所有 k 个数的排列，当 k 为 0 时候，将 flags 加入到 conbinations.
    void findCombinations(int start, int end, int k, set<int>& flags, vector<vector<int>>& combinations)
    {
        if(k == 0)
        {
            combinations.push_back(vector<int>(flags.begin(), flags.end()));
            return;
        }
        if(end - start < k)
        {
            return;
        }

        for(int i = start; i < end; ++i)
        {
            flags.insert(i);
            --k;
            findCombinations(i+1, end, k, flags, combinations);
            ++k;
            flags.erase(i);
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> combinations;
        set<int> flags;

        findCombinations(1, n+1, k, flags, combinations);
        return combinations;
    }
};