题解

题目描述

给定一个不含重复数字的数组$nums$，返回其所有可能的全排列。返回结果按照任意顺序即可。

思路

本题要求输出一个数组的所有排列组合，即求出数组的全排列。全排列是从数组的元素中挑选出所有元素的不同排列方式。可以使用回溯算法来求解这个问题。

回溯算法的核心思想是通过递归的方式尝试每个可能的情况，并在某个条件满足时记录当前的状态。当递归回溯到最深层时，所有的元素都已被选取一遍，表示形成了一种排列。

代码分析

1. 递归基础：

   • 首先，我们从数组的第一个元素开始，尝试将数组中每个元素放在当前空位上，并进行递归。
   • 每次递归调用时，需要确保当前元素未被使用（我们用一个布尔数组来标记）。
   • 每当数组中所有元素都被使用过一遍时，即形成一个完整的排列，记录下来。

2. 回溯：

   • 在递归过程中，如果当前元素已经被使用，我们就跳过当前元素；如果没有被使用，我们就把它加入当前的排列中，并继续递归。
   • 递归完成后，我们将当前元素标记为未使用，继续尝试其他的元素。

C++代码

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

class Solution {
public:
    // 结果存储
    vector<vector<int>> result;

    // 回溯函数
    void backtrack(vector<int>& nums, vector<int>& current, vector<bool>& used) {
        // 如果当前排列的长度和nums的长度相同，表示已经得到一个排列
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        
        // 遍历数组nums
        for (int i = 0; i < nums.size(); ++i) {
            // 如果元素已使用，跳过
            if (used[i]) continue;
            // 标记当前元素为已使用
            used[i] = true;
            // 选择当前元素并递归
            current.push_back(nums[i]);
            backtrack(nums, current, used);
            // 回溯，撤销选择
            current.pop_back();
            used[i] = false;
        }
    }

    // 主函数，启动回溯过程
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        vector<int> current;
        backtrack(nums, current, used);
        return result;
    }
};

// 用于输入输出
int main() {
    Solution solution;
    vector<int> nums;
    int num;
    
    // 读入数据
    while (cin >> num) {
        nums.push_back(num);
        if (cin.get() == '\n') break;
    }
    
    // 获取全排列
    vector<vector<int>> res = solution.permute(nums);
    
    // 输出结果
    for (const auto& perm : res) {
        for (int i = 0; i < perm.size(); ++i) {
            if (i != 0) cout << " ";
            cout << perm[i];
        }
        cout << endl;
    }
    
    return 0;
}

Python

class Solution:
    def permute(self, nums):
        result = []
        used = [False] * len(nums)
        current = []
        
        def backtrack():
            if len(current) == len(nums):
                result.append(current[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = True
                current.append(nums[i])
                backtrack()
                current.pop()
                used[i] = False
        
        backtrack()
        return result

# 输入输出部分
if __name__ == '__main__':
    nums = list(map(int, input().split()))
    solution = Solution()
    res = solution.permute(nums)
    for perm in res:
        print(" ".join(map(str, perm)))

Java

import java.util.*;

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        List<Integer> current = new ArrayList<>();
        
        backtrack(nums, result, current, used);
        return result;
    }
    
    private void backtrack(int[] nums, List<List<Integer>> result, List<Integer> current, boolean[] used) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.add(nums[i]);
            backtrack(nums, result, current, used);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }

        Solution solution = new Solution();
        List<List<Integer>> res = solution.permute(nums);

        for (List<Integer> perm : res) {
            for (int i = 0; i < perm.size(); i++) {
                if (i != 0) System.out.print(" ");
                System.out.print(perm.get(i));
            }
            System.out.println();
        }
    }
}

Leetcode 55.全排列-原题链接

题目内容

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

输入描述

输出描述

样例1

输入

1 2 3

输出

1 2 3 
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

样例2

输入

0 1

输出

0 1
1 0

样例3

输入

1

输出

1

提示

• $1 <= nums.length <= 6$
• $-10 <= nums[i] <= 10$
• $nums$中的所有整数互不相同