LeetCode 46. 全排列(Permutations)
时间:2022-05-05 23:30
题目描述
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
解题思路
回溯法,从第一个数开始,依次与此位置向后的每一个位置交换得到新序列,然后递归向后重复此动作,在得到某位置开头的所有序列后要把交换后的序列复原。
代码
1 class Solution { 2 public: 3 vector> permute(vector & nums) { 4 vector > res; 5 pmt(nums, 0, res); 6 return res; 7 } 8 void pmt(vector &seq, int idx, vector > &res){ 9 if(idx == seq.size() - 1) 10 res.push_back(seq); 11 else{ 12 for(int i = idx; i < seq.size(); i++){ 13 swap(seq[idx], seq[i]); 14 pmt(seq, idx + 1, res); 15 swap(seq[i], seq[idx]); 16 } 17 } 18 } 19 };