LeetCode: Permutations

一次过

 1 class Solution {
 2 public:
 3     void dfs(int dep, int maxdep, vector<int> &tmp, vector<vector<int>> &ret, vector<int> num, vector<bool> &visit) {
 4         if (dep == maxdep) {
 5             ret.push_back(tmp);
 6             return;
 7         }
 8         for (int i = 0; i < maxdep; i++) {
 9             if (!visit[i]) {
10                 visit[i] = true;
11                 tmp.push_back(num[i]);
12                 dfs(dep+1, maxdep, tmp, ret, num, visit);
13                 tmp.pop_back();
14                 visit[i] = false;
15             }
16         }
17     }
18     vector<vector<int> > permute(vector<int> &num) {
19         // Start typing your C/C++ solution below
20         // DO NOT write int main() function
21         sort(num.begin(), num.end());
22         int size = num.size();
23         vector<int> tmp;
24         vector<vector<int>> ret;
25         vector<bool> visit(size, false);
26         dfs(0, size, tmp, ret, num, visit);
27         return ret;
28     }
29 };

推荐下一段代码

 1 class Solution {
 2 public:
 3     void dfs(vector<int> &num, vector<vector<int> > &ans, int k) {
 4         if (k == num.size()) {
 5             ans.push_back(num);
 6             return;
 7         }
 8         for (int i = k; i < num.size(); ++i) {
 9             swap(num[i], num[k]);
10             dfs(num, ans, k+1);
11             swap(num[i], num[k]);
12         }
13     }
14     vector<vector<int> > permute(vector<int> &num) {
15         vector<vector<int> > ans;
16         if (num.size() == 0) return ans;
17         sort(num.begin(), num.end());
18         dfs(num, ans, 0);
19         return ans;
20     }
21 };

 1 public class Solution {
 2     public List<List<int>> Permute(int[] nums) {
 3         List<List<int>> ans = new List<List<int>>();
 4         if (nums.Length == 0) return ans;
 5         Array.Sort(nums);
 6         dfs(nums, ref ans, 0);
 7         return ans;
 8     }
 9     public void dfs(int[] nums, ref List<List<int>> ans, int k) {
10         if (k == nums.Length) {
11             ans.Add(new List<int>(nums));
12             return;
13         }
14         for (int i = k; i < nums.Length; i++) {
15             int tmp = nums[i];
16             nums[i] = nums[k];
17             nums[k] = tmp;
18             dfs(nums, ref ans, k+1);
19             tmp = nums[i];
20             nums[i] = nums[k];
21             nums[k] = tmp;
22         }
23     }
24 }

View Code