【2023】华为OD机试真题Java CC++ Python JS Go-题目0249-全排列

**华为OD机试真题 Java CC++ Python JS Go**

**题目0249: 全排列**

**问题描述:**

给定一个长度为 n 的整数数组 nums，返回所有可能的全排列。注意，每个整数在每个排列中出现次数相同。

**示例1:**

输入：nums = [1,2,3]
输出：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

**示例2:**

输入：nums = [0,1]
输出：
[
[0,1],
[1,0]
]

**示例3:**

输入：nums = [1]
输出：
[
[1]
]

**要求:**

* 必须使用 Java、CC++、Python、JS 或 Go语言之一编写代码。
* 必须实现一个函数或方法，能够返回所有可能的全排列。
* 必须保证每个整数在每个排列中出现次数相同。

**提示:**

* n 的值将小于等于9。
* nums 中的元素将是非负整数。

**解决方案:**

### Java 解决方案

javaimport java.util.*;

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

 private void backtrack(List> result, List tempList, int[] nums) {
 if (tempList.size() == nums.length) {
 result.add(new ArrayList<>(tempList));
 } else {
 for (int i =0; i < nums.length; i++) {
 if (!tempList.contains(nums[i])) {
 tempList.add(nums[i]);
 backtrack(result, tempList, nums);
 tempList.remove(tempList.size() -1);
 }
 }
 }
 }

 public static void main(String[] args) {
 Solution solution = new Solution();
 int[] nums = {1,2,3};
 List> result = solution.permute(nums);
 System.out.println(result);
 }
}

cpp#include <iostream>
#include <vector>

class Solution {
public:
 std::vector<std::vector<int>> permute(int* nums, int n) {
 std::vector<std::vector<int>> result;
 backtrack(result, {}, nums, n);
 return result;
 }

private:
 void backtrack(std::vector<std::vector<int>>& result, std::vector<int>& tempList, int* nums, int n) {
 if (tempList.size() == n) {
 result.push_back(tempList);
 } else {
 for (int i =0; i < n; i++) {
 if (!std::find(tempList.begin(), tempList.end(), nums[i]) != tempList.end()) {
 tempList.push_back(nums[i]);
 backtrack(result, tempList, nums, n);
 tempList.pop_back();
 }
 }
 }
 }

public:
 void printVector(const std::vector<std::vector<int>>& vec) {
 for (const auto& v : vec) {
 for (int num : v) {
 std::cout << num << " ";
 }
 std::cout << std::endl;
 }
 }

 int main() {
 int nums[] = {1,2,3};
 Solution solution;
 std::vector<std::vector<int>> result = solution.permute(nums,3);
 solution.printVector(result);
 return0;
 }
}

class Solution:
 def permute(self, nums):
 res = []
 self.backtrack(res, [], nums)
 return res def backtrack(self, res, tempList, nums):
 if len(tempList) == len(nums):
 res.append(tempList[:])
 else:
 for num in nums:
 if num not in tempList:
 tempList.append(num)
 self.backtrack(res, tempList, nums)
 tempList.pop()

# Test the functionnums = [1,2,3]
solution = Solution()
print(solution.permute(nums))

javascriptclass Solution {
 permute(nums) {
 let res = [];
 this.backtrack(res, [], nums);
 return res;
 }

 backtrack(res, tempList, nums) {
 if (tempList.length === nums.length) {
 res.push([...tempList]);
 } else {
 for (let num of nums) {
 if (!tempList.includes(num)) {
 tempList.push(num);
 this.backtrack(res, tempList, nums);
 tempList.pop();
 }
 }
 }
 }

 printArray(arr) {
 console.log(JSON.stringify(arr));
 }

 main() {
 let nums = [1,2,3];
 let solution = new Solution();
 let result = solution.permute(nums);
 solution.printArray(result);
 }
}

let solution = new Solution();
solution.main();

gopackage mainimport (
"fmt"
)

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

func backtrack(res *[][]int, tempList []int, nums []int) {
	if len(tempList) == len(nums) {
*res = append(*res, append([]int{}, tempList...))
}
	for _, num := range nums {
	if !contains(tempList, num) {
	tempList = append(tempList, num)
	backtrack(res, tempList, nums)
	tempList = tempList[:len(tempList)-1]
}
}
}

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

func main() {
	nums := []int{1,2,3}
	solution := permute(nums)
	fmt.Println(solution)
}