本文共 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/