[Leetcode] Permutations 置换

深度优先搜索

复杂度

时间 O(N) 空间 O(N) 递归栈

思路

置换实际上是给出所有的排列方式，同样是用深度优先搜索，不过为了避免重复选择的情况，我们要保证两点：第一，所有数必须是数组中的，第二，数组中每个数只能用不多于也不少于一次。如果我们要单独写一个函数，来判断下一轮搜索该选择哪一个数就很麻烦了。这里有一个技巧，我们可以只将数两两交换，不过交换时只能跟自己后面的交换。

代码

public class Solution {        List<List<Integer>> res;        public List<List<Integer>> permute(int[] nums) {        res = new LinkedList<List<Integer>>();        helper(nums, 0);        return res;    }        public void helper(int[] nums, int i){        // 找到转置完成后的解，将其存入列表中        if(i == nums.length - 1){List<Integer> list = new LinkedList<Integer>();for(int j = 0; j < nums.length; j++){    list.add(nums[j]);}res.add(list);        }        // 将当前位置的数跟后面的数交换，并搜索解        for(int j = i; j < nums.length; j++){swap(nums, i , j);helper(nums, i + 1);swap(nums, i, j);        }    }        private void swap(int[] nums, int i, int j){        int tmp = nums[i];        nums[i] = nums[j];        nums[j] = tmp;    }}