LeetCode--46. Permutations

题目链接：https://leetcode.com/problems/permutations/

昨天是组合的题目，今天是排列问题，排列的题目就是对于每个元素在某个特定位置上到底选不选的问题。而在前面的位置上选了的某个元素在后面的位置上是不能选的。这时就需要一个全局数组visited来记录选了的与没选的情况。与组合一样，我会用一个ret来存储所有符合条件的排列情况最终返回，而用record数组记录某个符合条件的排列情况（因为每种排列情况的选择次数是固定的）。比如在第i个位置上我选了待选数组中第j个元素，那么在第i+1，i+2,....的位置上就不能再选第j个元素；在第i个位置上我没选待选数组中第j个元素，那么在第i+1，i+2,....的位置上就可以再选第j个元素了。当当前一个选择的后续选择都做完时（递归函数层层深入），跳出当前的递归函数时需要将该位置上选择记录给复位。

这样这个题目就很简单了：

class Solution {
    
    public static List<List<Integer>> ret;
    public static boolean[] visited;
    public static int[] record;
    public static int num;
    
    public List<List<Integer>> permute(int[] nums) {
        
        ret=new LinkedList<List<Integer>>();
        num=nums.length;
        record=new int[num];
        visited=new boolean[num];
        recursive(nums,num);
        return ret;
    }
    
    public static void recursive(int[] nums,int k)
    {
        if(k==0)
        {
            LinkedList<Integer> tmp=new LinkedList<Integer>();
            for(int i=0;i<num;i++)
                tmp.add(record[i]);
            ret.add(tmp);
        }
        for(int i=0;i<nums.length;i++)
        {
            if(!visited[i])
            {
                record[k-1]=nums[i];
                visited[i]=true;
                recursive(nums,k-1);
                visited[i]=false;
            }
        }
    }
}