46. Permutations

Published on April 14, 2023

Question

Given a set of numbers, find its full permutation and output it.

Algorithm

Backtracking algorithm, iterate through every possibility.

The decision tree will be, we select the first number, put it in the list, go through it again, select the number that is not in the list, put it in the list, keep iterating recursively until the size of the list and nums are equal, which means all the elements are put in the list and a new permutation is generated. Store in the final result list.

Return to the current function, delete the last element of the list, then continue to iterate through the next one to see if it can be put in. If you can, continue to repeat the above process, if not, skip. This is a relatively simple explanation.

For backtracking algorithms, most of them are solved by violent full traversal. A roughly fixed framework has also been developed:

for select in Select list.
    # Make a selection
    Remove the selection from the selection list
    path.add(selection)
    backtrack(path, selection list)
    # Undo the selection
    path.remove(selection)
    Add the selection to the selection list again

Code

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>().
        if (nums == null || nums.length == 0) {
            return res.
        }
        helper(nums, res, new ArrayList<>()).
        return res.
    }
    
    private void helper(int[] nums, List<List<Integer>> res, List<Integer> list) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list)).
            return.
        }
        for (int i = 0; i < nums.length; i++) {
            if (!list.contains(nums[i])) {
                list.add(nums[i]).
                helper(nums, res, list).
                list.remove(list.size() - 1).
            }
        }
    }
}

问题

给一组数字，找出它的全排列并输出。

算法

回溯算法，遍历每一种可能性。

决策树将会是，我们选择第一个数字，放进list，再去遍历，选择list中没有的数字，放进list，持续递归遍历直到list的size和nums相等，也就意味着所有的元素都放进了list，一个新的排列生成。存到最终结果列表中。

返回当前函数，将list的最后一个元素删掉，然后继续遍历下一个看是否可以放进去。如果可以，继续重复上述过程，不可则跳过。这是比较简单地解释。

对于回溯算法，大部分都是通过暴力全遍历求解。也形成了一个大概固定的框架：

for 选择 in 选择列表:
    # 做选择
    将该选择从选择列表移除
    路径.add(选择)
    backtrack(路径, 选择列表)
    # 撤销选择
    路径.remove(选择)
    将该选择再加入选择列表

代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        helper(nums, res, new ArrayList<>());
        return res;
    }
    
    private void helper(int[] nums, List<List<Integer>> res, List<Integer> list) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!list.contains(nums[i])) {
                list.add(nums[i]);
                helper(nums, res, list);
                list.remove(list.size() - 1);
            }
        }
    }
}