图解算法——全排列（Permutations）

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Input: nums = [1]
Output: [[1]]

//全排列
/*
有两种思路：一是原地调换位置，二是树状分布
*/

class Solution{
    
    //数字全排列
    public List> permute(int[] nums) {
        
        List> res = new List>;
        List arr = new ArrayList;
        boolean[] is = new boolean(nums.length)//表示该下标所在字符是否存在：fasle表示不存在，true表示存在;
        search(res,arr,nums,is);
        return res;
    }
    public void search(List> res, List arr, int[] nums, boolean[] is){
        if(arr.size() == nums.length){
            res.add(arr);
            return;
        }
        for(int i = 0; i){
            if(is[i]){
                continue;
            }
            is[i] = true;
            arr.add(nums[i]);
            search(res,arr,nums,is);  //是一个子问题
            arr.remove(nums[i]);
            is[i] = false;
        }
    }
    //字符串全排列
    public void permute1(string str) {
        char[] chs = str.toCharArray();
        List res = new ArrayList;
        process(res,chs,0);
    }
    
    public void process(List res, char[] chs,int i){
        if(i==chs.length){
            res.add(chs.toString());
            return;
        }
        for(int j=i; j){
            swap(chs,i,j);
            process(res,chs,++i);
            swap(chs,i,j);
        }
    }
    public void process(char[] chs,int i,int j){
        int temp = chs[i];
        chs[i] = chs[j];
        chs[j] = temp;
    }
}