首页 > 代码库 > [leetcode]Combinations
[leetcode]Combinations
问题描述:
Given two integers n and k, return all possible combinations ofk 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],
]
基本思想:
回溯法
代码:
vector<int> record; //C++ vector<vector<int> >result; set<vector<int> > myset; int kNum = 0; void addSolution(){ vector<int> tmp(record.begin(),record.end()); sort(tmp.begin(),tmp.end()); if(myset.find(tmp) == myset.end()){ result.push_back(tmp); myset.insert(tmp); } } void subCombinationSum(vector<int> &cadidates,int bpos,vector<int> &base, int k){ if(kNum == k){ addSolution(); } int size = cadidates.size(); for(int i = bpos; i < size; i++){ if(base[i] == 1) continue; record.push_back(cadidates[i]); base[i] = 1; kNum++; subCombinationSum(cadidates,<span style="color:#FF0000;"><strong>i+1</strong></span>,base,k); //i+1 避免重复 record.pop_back(); base[i] = 0; kNum--; } } vector<vector<int> > combine(int n, int k) { vector<int> candidates(n); for(int i = 0; i < n; i++) candidates[i] = i+1; vector<int> base(candidates.size(),0); subCombinationSum(candidates,0,base,k); return result; }
[leetcode]Combinations
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。