【LeetCode】77. Combinations，DFS的变形应用

冷不防 2022-07-26 11:20 132阅读 0赞

77. Combinations

Total Accepted: 72222 Total Submissions: 212130 Difficulty: Medium

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

【分析】

很明显，本题是一个组合问题，从给定的数据中寻找所有指定长度的组合，可采用**深度优先搜索（DFS）**来解决，从1开始搜索，搜索结束的条件为存入组合容器的数据个数等于k，此时将此组合存入结果容器，然后弹出组合容器顶部数据，继续搜索，直到所有路径全部遍历。由于本题中给定数据n的长度可能大于组合长度k，且无重复，因此，在进行深度搜索时需注意每一次向组合容器中添加数据的约束条件：temp.size()==LengthOfCom-k，具体见程序

【解法】

class Solution {
    public:
        vector<vector<int>> combine(int n, int k) 
        {
            vector<int> temp;//存放组合
            if(n<k||n==0||k==0)return result;//异常容错
    	int lengthOfCom=k;//指定组合长度
            DFS(1,temp,n,k,lengthOfCom);//深度搜索
            return result;
        }
        
    private:
    
        vector<vector<int>> result;//存储所有组合结果
        
        void DFS(int begin,vector<int>& temp,int n,int k,int LengthOfCom)
        {
            //k==0表明组合容器已满，本次搜索结束，将组合存入结果容器并返回
             if(k==0)
    		{
    			result.push_back(temp);
    			return;
    		}
    
    	for(int i=begin;i<=n;i++)//每一次搜索的起点从上一次的下一个数开始，没有重复
            {
                 if(temp.size()==LengthOfCom-k)//<span style="color:#ff0000;">由于这里的深度k小于等于n，加此约束，避免组合数据超量</span>
    		temp.push_back(i);
                 searchSolution(i+1,temp,n,k-1,LengthOfCom);//搜索下一个组合数，k-1，
    	
                    temp.pop_back();//深度达到k时，保存组合，弹出顶端元素，继续搜索
            }
        }
    };