LeetCode 46. 全排列

Categories:

题目描述
思路分析
参考代码
相似题目

题目描述

🔥 46. 全排列

思路分析

回溯算法

参考代码

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return [][]int{}
	}
	res := make([][]int, 0)
	backtrack(nums, []int{}, &res)
	return res
}

func backtrack(nums []int, path []int, res *[][]int) {
	if len(nums) == len(path) {
		temp := make([]int, len(path))
		copy(temp, path)
		*res = append(*res, temp)
		return
	}
	for _, num := range nums {
		if contains(path, num) {
			continue
		}
		path = append(path, num)
		backtrack(nums, path, res)
		path = path[:len(path)-1]
	}
}

func contains(nums []int, target int) bool {
	for _, num := range nums {
		if num == target {
			return true
		}
	}
	return false
}

🍏 点击查看 Java 题解

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), res);
        return res;
    }

    public void backtrack(int[] nums, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int num : nums) {
            if (path.contains(num)) {
                continue;
            }
            path.add(num);
            backtrack(nums, path, res);
            path.remove(path.size() - 1);
        }
    }
}

相似题目

题目	难度	题解
下一个排列	Medium
全排列 II	Medium
排列序列	Hard
组合	Medium

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/83334596