[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],
]

思路

典型的递归回溯法。
（1）递归一次，填入一个数字
（2） 填入的数字，不能是小于当前数字的值，防止重复
（3 ）回溯：记得pop_back()最后加上的一个数字，回溯到上一层。
（4） 结束条件：填写够了k个数字的时候，当前填写完毕，回溯

代码

    /**------------------------------------
    *   日期：2015-02-06
    *   作者：SJF0115
    *   题目: 77.Combinations
    *   网址：https://oj.leetcode.com/problems/combinations/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        vector<vector<int> > combine(int n, int k) {
            vector<vector<int> > result;
            vector<int> path;
            DFS(n,k,result,path,1);
            return result;
        }
    private:
        void DFS(int n,int k,vector<vector<int> > &result,vector<int> &path,int index){
            if(path.size() == k){
                result.push_back(path);
                return;
            }//if
            for(int i = index;i <= n;++i){
                path.push_back(i);
                DFS(n,k,result,path,i+1);
                path.pop_back();
            }//for
        }
    };

    int main(){
        Solution s;
        int n = 5;
        int k = 2;
        vector<vector<int> > result = s.combine(n,k);
        // 输出
        for(int i = 0;i < result.size();++i){
            for(int j = 0;j < k;++j){
                cout<<result[i][j]<<" ";
            }//for
            cout<<endl;
        }//for
        return 0;
    }

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>