首页 > 代码库 > Combinations C++

Combinations C++

2024-07-15 21:38:10   209人阅读

Question: Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

要产生全部的combinations，我们需要一种有序的方式产生combination以达到既产生全部又没有重复的目的。一个很简单的想法便是将[1,n]分成两个区间[1,k][k+1,n]，然后交换两个区间中的1、2....min(k,n-k)个数。但这个方法，代码繁琐。在查找了网上的解答后，发现一种方法很好，代码简单，也易理解。

其主要想法是，先在[1,n]上抽象出一个有向图结构，如果节点i < j，那么有一条从i指向j的边。然后在这个有向图上，利用DFS，找出所有长度为k的path。

 1 class Solution { 2 public: 3     vector<vector<int> > combine(int n, int k) { 4         vector<vector<int>> res; 5         vector<int> path; 6         dfs_combine(n,k,1,0,path,res); 7         return res; 8     } 9     void dfs_combine(int n, int k, int start, int length, vector<int> & path, vector<vector<int>> & res){10         if(length == k) res.push_back(path);11         for(int i = start; i <= n; i++){12             path.push_back(i);13             dfs_combine(n,k,i+1,length+1,path,res);14             path.pop_back();15         }16     }17 };

 


联系
我们