没有重复项数字的所有排列

示例说明

以下是数字 1, 2, 3 的所有排列，输出顺序按字典序排列：

[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]

代码实现

方法思路

我们可以使用递归的方法来解决获得所有排列问题。递归的基本思路是逐步选择数字并记录选择情况，直到所有位置都被填满为止。具体来说，我们可以使用一个布尔数组来跟踪已经选择的数字位置，避免重复项排列。

递归实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;class Solution {    vector
        
         
          > result; vector
          
            res; void dfs(vector
           
             num, deque
            
              used) { if (res.size() == num.size()) { result.push_back(res); return; } for (int i = 0; i < num.size(); ++i) { if (used[i]) continue; res.push_back(num[i]); used[i] = true; dfs(num, used); res.pop_back(); used[i] = false; } } vector
             
               permutate(vector
              
                num) { int nsize = num.size(); deque
               
                 used(nsize, false); dfs(num, used); sort(num.begin(), num.end()); return result; }};

逐步说明

问题分析

给定一组没有重复项的数字，要求生成该数字的所有排列并按字典序输出。例如，数字 [1, 2, 3] 的所有排列包括 [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]。

递归原理

遍历每个数字，依次将其添加到结果列表中。如果当前结果的长度等于输入数字的长度，则将该排列添加到结果列表中。然后回溯（撤销选择），继续尝试下一个数字。

去重和排序

在回溯结束后，对结果列表进行排序，以确保输出顺序符合字典序要求。

代码结构

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;class Solution {private:    vector
        
         
          > result; vector
          
            res;public: vector
           
             permutate(vector
            
              num) { int nsize = num.size(); deque
             
               used(nsize, false); dfs(num, used); sort(num.begin(), num.end()); return result; }private: void dfs(vector
              
                num, deque
               
                 used) { if (res.size() == num.size()) { result.push_back(res); return; } for (int i = 0; i < num.size(); ++i) { if (used[i]) continue; res.push_back(num[i]); used[i] = true; dfs(num, used); res.pop_back(); used[i] = false; } }};

总结

通过上述方法，我们可以高效地生成没有重复项数字的所有排列，并确保输出结果符合字典序要求。该方法利用回溯算法逐个选择和排除数字，避免了重复项的生成，适合处理较小规模的数字集合。

转载地址：http://egdhz.baihongyu.com/

你可能感兴趣的文章