leetcode 77.组合

	给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。



	你可以按 任何顺序 返回答案。



	
	

		class Solution {
	

	

		public: 
	

	

		    vector<vector<int>> combine(int n, int k) {
	

	

		        vector<vector<int>> res;
	

	

		        vector<int> path;
	

	

		        dfs(n, k, res, path, 1);
	

	

		        return res;
	

	

		    }
	

	

		    void dfs(int n, int k, vector<vector<int>>& res, vector<int>& path, int index){
	

	

		        if(path.size()==k){
	

	

		            res.push_back(path);
	

	

		            return;
	

	

		        }
	

	

		//剪枝
	

	

		
		

			
			

				
				

					已经选择的元素个数：path.size();
				

			

			

				
				

					还需要的元素个数为: k - path.size();
				

			

			

				
				

					在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
				

			

		

		

			为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
		

		

			举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
		

		

			从2开始搜索都是合理的，可以是组合[2, 3, 4]。
		

		

			这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。
		

	

	

		        for(int i=index; i<=n-(k-path.size())+1; i++){
	

	

		            path.push_back(i);
	

	

		            dfs(n, k, res, path, i+1);
	

	

		            path.pop_back();
	

	

		        }
	

	

		    }
	

	

		};