leetcode 46. Permutations 全排列问题+递归

心已赠人 2022-06-09 10:18 192阅读 0赞

Given a collection of distinct numbers, return all possible permutations.

For example,  
\[1,2,3\] have the following permutations:  
\[  
\[1,2,3\],  
\[1,3,2\],  
\[2,1,3\],  
\[2,3,1\],  
\[3,1,2\],  
\[3,2,1\]  
\]

这道题考察的就是全排列，直接使用递归即可解决。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class Solution 
    {
        
        public List<List<Integer>> permute(int[] nums) 
        {
            //特殊情况
            List<List<Integer>> res=new ArrayList<>();
            if(nums==null || nums.length<=0)
                return res;
    
            //就是一个全排列问题
            fullPermute(res,nums,0,nums.length);
            return res;
        }
    
        private void fullPermute(List<List<Integer>> res, int[] nums, int beg, int length)
        {
            if(beg==length)
            {
                List<Integer> tt=new ArrayList<>();
                for(int j=0;j<length;j++)
                    tt.add(nums[j]);
                res.add(tt);
            }else
            {
                for(int j=beg;j<length;j++)
                {
                    int tmp=nums[beg];
                    nums[beg]=nums[j];
                    nums[j]=tmp;
    
                    fullPermute(res, nums, beg+1, length);
    
                    tmp=nums[beg];
                    nums[beg]=nums[j];
                    nums[j]=tmp;    
                }
            }   
        }
    }

下面是C++的做法，是一道很经典的DFS深度优先遍历的做法

代码如下:

#include <iostream>
    #include <regex>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<vector<int>> res;
        vector<vector<int>> permute(vector<int>& nums) 
        {
            if (nums.size() <= 1)
            {
                res.push_back(nums);
                return res;
            }
            getAll(nums, 0);
            return res;
        }
    
        void getAll(vector<int>& nums, int beg)
        {
            if (beg == nums.size())
            {
                res.push_back(nums);
                return;
            }
            else
            {
                for (int i = beg; i < nums.size(); i++)
                {
                    int tmp = nums[beg];
                    nums[beg] = nums[i];
                    nums[i] = tmp;
    
                    getAll(nums, beg + 1);
    
                    tmp = nums[beg];
                    nums[beg] = nums[i];
                    nums[i] = tmp;
                }
            }
        }
    };