【题目描述】
https://leetcode.cn/problems/permutations/?favorite=2cktkvj
给定一个不含重复数字的数组 nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案
【示例】
【代码1】
学习参考
package com.company;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class Test {
List<List<Integer>> result = new ArrayList<>(); // 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>(); // 存放符合条件结果(已经选择了那些元素)
public List<List<Integer>>permute(int[] nums){
if (nums.length == 0 ) return result;
backtrack(nums, path);
return result;
}
private void backtrack(int[] nums, LinkedList<Integer> path) {
if(nums.length == path.size()) {
result.add(new ArrayList<>(path));
}
for(int i = 0; i < nums.length; i++){
if(path.contains(nums[i])){
continue;
}
path.add(nums[i]);
backtrack(nums, path);
path.removeLast();
}
}
}
public class threeSum {
public static void main(String[] args) {
int[] arr = {1, 2, 3};
System.out.println(new Test().permute(arr).toString());
}
}
【代码2】
学习参考
package com.company;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class Test {
List<List<Integer>> result = new ArrayList<>(); // 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>(); // 存放符合条件结果
boolean[] used; // 当前的数字是否已经被选择过 O(1)
public List<List<Integer>> fullArray(int[] nums) {
if(nums.length == 0){
return result;
}
// 如果节点不为空, 则初始化used数组
used = new boolean[nums.length];
permuteHelper(nums);
return result;
}
private void permuteHelper(int[] nums) {
if(path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++){
if(used[i]) {
continue;
}
used[i] = true; // 当前所处位置
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}
public class threeSum {
public static void main(String[] args) {
int[] arr = {1, 2, 3};
System.out.println(new Test().fullArray(arr).toString());
}
}
【回溯算法】
回溯算法(点击查看) = 递归(数量够了就停止) + 回溯(状态重置)
模板框架如下:回溯算法模板框架如下:
标签:排列,LinkedList,nums,46,int,LeeCode,result,new,path From: https://blog.51cto.com/u_13682316/5888017