combinations@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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

» Solve this problem

这些题都和permutations一个思路，把permutations给弄明白了，这些枚举的方法就搞定了，其实这些题的本质就是搜索，或者search，又或者是pointers题，就是用一种正确而且全面的方式去搜索这个数据结构。很多算法的本质也是做同一件事情，比如树的遍历，比如图的bfs, dfs， 全都是一种如何去遍历or iterate through一个数据结构的方法。

写熟一点儿，发现pattern。

	class Solution {
	public:
	void findCombine(int n, int k, vector<int> &visited, vector<int> &sol, vector<vector<int> > &res)
	{
	if(sol.size()==k)
	{
	res.push_back(sol);
	return;
	}
	for(int i=1; i<=n; i++)
	{
	if(visited[i-1]==0)
	{
	if(sol.size()==0||sol.back()<i)
	{
	visited[i-1]=1;
	sol.push_back(i);
	findCombine(n, k, visited, sol, res);
	sol.pop_back();
	visited[i-1]=0;
	}
	}
	}
	}
	vector<vector<int> > combine(int n, int k) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<int> sol;
	vector<vector<int> > res;
	if(n==0||k==0) return res;
	vector<int> visited(n, 0);
	findCombine(n, k, visited, sol, res);
	return res;
	}
	};

view raw combinations hosted with ❤ by GitHub

	class Solution {
	public:
	void helper(vector<vector<int> > &res, vector<int> &tmp, int begin, int end, int k){
	if(tmp.size() == k){
	res.push_back(tmp);
	return;
	}
	for(int i=begin; i<=end; i++){
	tmp.push_back(i);
	helper(res, tmp, i+1, end, k);
	tmp.pop_back();
	}
	}
	vector<vector<int> > combine(int n, int k) {
	vector<vector<int> >res;
	if(n==0||k==0) return res;
	vector<int> tmp;
	//vector<int> visited(n, 0);
	helper(res, tmp, 1, n, k);
	return res;
	}
	};

view raw Combinations hosted with ❤ by GitHub