leetcode46：全排列

题目链接

leetcode

题目描述

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。
你可以按任意顺序返回答案。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    回溯

    从前往后，一位一位枚举，每次选择一个没有被使用的数。
    选好之后，将该数的状态改为“已被使用”，同时将该数记录在相应位置，然后递归。
    细节：递归返回时，将该数的状态改为“未被使用”，并将该数从相应位置上删除。

    时间复杂度：O(n*n!)
        其中 n 是数字的数量。
        对于每个数字，都有两种选择：使用或不使用，共有 n! 种可能的排列。
        因此，总的时间复杂度是 O(n*n!)。
    空间复杂度：O(n)
        除答案数组以外，在递归过程中需要为每一层递归函数分配栈空间，
        所以空间取决于递归的深度，递归调用深度为 O(n)。
*/
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        visited = vector<bool>(nums.size(), false);
        dfs(nums);
        return result;
    }

    void dfs(vector<int>& nums) {
        // 结束条件：找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // 当前数字已经被访问，跳过
            if (visited[i]) {
                continue;
            }

            // 选择
            path.push_back(nums[i]);
            visited[i] = true;
            // 递归下一层
            dfs(nums);
            // 撤销选择
            path.pop_back();
            visited[i] = false;
        }
    }

private:
    vector<vector<int>> result; // 结果数组
    vector<int> path;           // 记录回溯的路径
    vector<bool> visited;       // 标记数组：标记路径中的元素，避免重复使用
};

int main() {
    Solution solution;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> permutations = solution.permute(nums);
    cout << "All permutations of ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << "are:" << endl;
    for (const vector<int>& permutation : permutations) {
        for (int num : permutation) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
    回溯法：
        使用回溯法（DFS）生成所有可能的排列。
        使用一个布尔数组 visited 来记录每个数字是否已经被访问过。
        每次递归时，选择一个未访问的数字，将其加入当前路径，并标记为已访问。
        递归完成后，撤销选择，恢复状态，继续尝试下一个数字。
    边界条件：
        如果数组长度为 1，直接返回包含该数组的列表。

   时间复杂度：O(n*n!)
        生成所有排列的时间复杂度为 O(n!)，其中 n 是输入数组的长度。
        每个排列的生成时间复杂度为 O(n)，因为需要将路径复制到结果列表中。
        因此，总时间复杂度为 O(n*n!)。
   空间复杂度：O(n!)
       结果列表 res 的空间复杂度为 O(n!)，存储所有排列。
       递归调用栈的深度为 O(n)。
       path 和 visited 数组的空间复杂度为 O(n)。
       因此，总空间复杂度为 O(n!)。
*/
func permute(nums []int) [][]int {
    n := len(nums)
    result := [][]int{} // 存储所有排列的结果
    path := []int{}     // 访问路径
    visited := make([]bool, n) // 标记每个数字是否已经被访问

    var dfs func()
    dfs = func() {
        // 结束条件：路径长度等于 nums 的长度，说明找到了一个完整的排列
        if len(path) == n {
            result = append(result, append([]int{}, path...))
            return
        }

        // 遍历数组，尝试每个数字
        for i := 0; i < n; i++ {
            // 剪枝：当前数字已经被访问，跳过
            if visited[i] {
                continue
            }
            
            // 选择当前数字
            path = append(path, nums[i])
            visited[i] = true
           // 递归处理下一个数字
            dfs()
            // 回溯，撤销选择
            path = path[:len(path)-1]
            visited[i] = false
        }
    }

    dfs()
    return result
}

func main() {
    // 测试用例
    testCases := []struct {
        nums     []int
        expected [][]int
    }{
        {
            nums: []int{1, 2, 3},
            expected: [][]int{
                {1, 2, 3}, {1, 3, 2}, {2, 1, 3},
                {2, 3, 1}, {3, 1, 2}, {3, 2, 1},
            },
        },
        {
            nums: []int{0, 1},
            expected: [][]int{
                {0, 1}, {1, 0},
            },
        },
        {
            nums: []int{1},
            expected: [][]int{
                {1},
            },
        },
    }

    for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
        result := permute(tc.nums)
        resultStr := fmt.Sprint(result)
        expectedStr := fmt.Sprint(tc.expected)

        if resultStr == expectedStr {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %d)\n", i+1, resultStr, expectedStr)		
        }
    }
}