博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetCode 77 组合(dfs,回溯)
阅读量:253 次
发布时间:2019-03-01

本文共 698 字,大约阅读时间需要 2 分钟。

题目链接:

题目描述:

给定一个整数 n 和一个整数 k,求在 1 n 中选取 k 个数字的所有组合方法。

输入输出:

输入: n = 4, k = 2输出:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]

题目分析: 

类似于排列问题,我们也可以进行回溯。排列回溯的是交换的位置,而组合回溯的是否把当前的数字加入结果中。

vector
> combine(int n,int k){ vector
>ans; vector
comb(k,0);//comb数组用来储存大小为k数组的排列方式 int count=0; backtracking(ans,comb,count,1,n,k); return ans; }void backtracking(vector
>&ans,vector
&comb,int &count,int pos,int n,int k){ if(count==k)//count计数器用来记录comb元素多少 { ans.push_back(comb); return ; } for(int i=pos;i<=n;++i) { comb[count++]=i;//修改当前节点状态 backtracking(ans,comb,count,i+1,n,k);//递归子节点 --count;//回改当前节点状态 }}

 

转载地址:http://kxlx.baihongyu.com/

你可能感兴趣的文章