给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）
数据范围：数字个数 
要求：空间复杂度 )
，时间复杂度 
[编程题]没有重复项数字的全排列
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型一维数组
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> permute (int[] num) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
dfs(num, res, new ArrayList<>(), 0);
return res;
}
void dfs(int[] num, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> t,
int index) {
if (t.size() == num.length) {
res.add(new ArrayList<>(t));
return;
}
for (int i = 0; i < num.length; i++) {
if(t.contains(num[i])){
continue;
}
t.add(num[i]);
dfs(num, res, t, i + 1);
t.remove(t.size() - 1);
}
}
}
发表于 2025-10-17 22:50:13
回复(0)
依照C++ STL的next_permutation()函数实现就好了。
但注意next_permutation()函数只会找字典序更大的排列，因此最开始要把数组从小到大排序，避免漏情况。
class Solution {
public:
vector<vector<int> > permute(vector<int>& num) {
vector<vector<int>> ans;
sort(num.begin(), num.end());
do {
ans.push_back(num);
} while (next_permutation(num.begin(), num.end()));
return ans;
}
}; import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> permute (int[] num) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
Arrays.sort(num);
do {
ArrayList<Integer> tmp = new ArrayList<>();
for (int n : num) tmp.add(n);
ans.add(tmp);
} while (nextPermutation(num));
return ans;
}
public boolean nextPermutation(int[] nums) {
if (nums.length <= 1) return false;
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
return i >= 0;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start) {
int left = start, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
}
编辑于 2025-02-25 11:33:25
回复(0)
public class Solution {
public ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
boolean[] used = new boolean[num.length];
ArrayList<Integer> currentPermute = new ArrayList<>();
backtrack(num, res, currentPermute, used);
return res;
}
public static void backtrack(int[] num,
ArrayList<ArrayList<Integer>> res, ArrayList<Integer> currentPermute,
boolean[] used) {
int n = num.length;
if (currentPermute.size() == n) res.add(new ArrayList<>(currentPermute));
else {
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
currentPermute.add(num[i]);
backtrack(num, res, currentPermute, used);
used[i] = false;
currentPermute.remove(currentPermute.size() - 1);
}
}
}
}
发表于 2024-10-16 23:29:35
回复(0)
public ArrayList<ArrayList<Integer>> permute (int[] num) {
return permute1(num);
}
public ArrayList<ArrayList<Integer>> permute1 (int[] num) {
ArrayList<ArrayList<Integer>> l = new ArrayList<>();
ArrayList<Integer> ll = new ArrayList<>();
for(int i=0;i<num.length;i++){
ll.add(num[i]);
}
permute1_1(l,ll,0);
return l;
}
public void permute1_1 (ArrayList<ArrayList<Integer>> l,ArrayList<Integer> ll,int pos) {
if(pos == ll.size()){
l.add(ll);
return;
}
for(int i=pos;i<ll.size();i++){
ArrayList<Integer> lt = new ArrayList<>(ll);
int t = lt.get(i);
lt.remove(i);
lt.add(pos,t);
permute1_1(l,lt,pos+1);
}
}
发表于 2024-08-26 14:00:36
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型一维数组
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> permute (int[] num) {
// write code here
// 左程云老师讲过全排列的分支限界递归法解决不重复全排列问题
// 调用一个递归函数，这个递归函数负责对当前i位置的数字进行与i ~ num.length - 1中的位置依次互换，然后继续考察i + 1处的情况
// 算法的时间复杂度0(N!)，额外空间复杂度0(N!)
// 用于记录所有路径的结果
ArrayList<ArrayList<Integer>> finalResults = new ArrayList<>();
// 调用这个递归函数，从num数组的0位置开始，将每一次找到的oneResult填进finalResult中
process(num, finalResults, 0);
// 返回最终的答案finalResults
return finalResults;
}
public void process(int[] num, ArrayList<ArrayList<Integer>> finalResults, int i) {
// 递归出口（底部）
if (i == num.length) {
// i越界了，说明整个数组遍历完毕了，将单个路径上的答案oneResult写入总答案finalResults中
// 踩坑点1：这里一定要【现场新创建】一个ArrayList放入答案中，如果提前在主方法创建好，那么随着每次递归的调用，finalResults里面的值也会被修改
ArrayList<Integer> oneResult = new ArrayList<>();
for (Integer n : num) {
oneResult.add(n);
}
finalResults.add(oneResult);
}
// 递归分支
for (int j = i; j < num.length; j++) {
// 将num[j]算入这次的结果中
swap(num, i, j);
// 在算入num[j]的基础上继续考察num数组中i+1往后的位置
process(num, finalResults, i + 1);
// 注意！恢复现场，继续尝试将将num[j+1]算入这次的结果中
// 踩坑点2：一定要【恢复现场】，要不然无法准确列出要分支的情况
swap(num, j, i);
}
}
// 数组元素交换函数
public void swap(int[] num, int i, int j) {
if (i == j) {
return;
}
int t = num[i];
num[i] = num[j];
num[j] = t;
}
}
发表于 2024-07-28 21:44:23
回复(1)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型一维数组
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> permute (int[] num) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
//排序
Arrays.sort(num);
List<Integer> numList = new ArrayList<>();
for (int n : num) {
numList.add(n);
}
solve(numList, res, new ArrayList<>());
return res;
}
private void solve(List<Integer> numList, ArrayList<ArrayList<Integer>> res,
List<Integer> path) {
if (path.size() == numList.size()) {
res.add(new ArrayList<>(path));
return;
}
for (Integer n : numList) {
if (path.contains(n)) {
continue;
}
path.add(n);
solve(numList, res, path);
path.remove(path.size() - 1);
}
}
}
发表于 2024-07-16 15:58:09
回复(0)
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> permute (int[] num) {
// write code here
Arrays.sort(num);
recur(num ,new boolean[num.length] ,new ArrayList<>());
return res;
}
public void recur(int[] num ,boolean[] flag ,ArrayList<Integer> list){
if(list.size()==num.length){
res.add(new ArrayList<>(list));
return;
}
for(int i=0;i<num.length;i++){
if((i>0 && num[i]==num[i-1] && !flag[i]) || flag[i]){
continue;
}
list.add(num[i]);
flag[i]=true;
recur(num ,flag ,list);
flag[i]=false;
list.remove(list.size()-1);
}
}
编辑于 2024-03-10 13:21:22
回复(0)
从上图可以看出，当只有到遍历到叶子节点才会得到一个排列结果，因此递归出口是是使用完所有的数字，也就是这个存放排列组合的栈的大小等于数组的长度；
if(num.length == list.size()){
res.add(new ArrayList<>(list));
return;
} 递归回溯套路 1.选择
2.递归/回溯
3.撤销选择
public class Solution {
public ArrayList<ArrayList<Integer>> permute (int[] num) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
LinkedList<Integer> list = new LinkedList<>();
boolean[] visit = new boolean[num.length];
dfs(num,res,list,visit);
return res;
}
private void dfs(int[] num, ArrayList<ArrayList<Integer>> res, LinkedList<Integer> list, boolean[] visit) {
if(num.length == list.size()){
res.add(new ArrayList<>(list));
return;
}
for(int i=0;i<num.length;i++){
if(visit[i]){
continue;
}
visit[i] = true;
list.add(num[i]);
dfs(num,res,list,visit);
list.pollLast();
visit[i] = false;
}
}
}
编辑于 2024-01-29 17:23:25
回复(0)
public ArrayList<ArrayList<Integer>> permute (int[] num) {
ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
ArrayList<Integer> list=new ArrayList<>();
build(num,ans,list);
return ans;
}
public void build(int[] num,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> list){
if(list.size()==num.length){ //截至条件（终止条件）
ans.add(new ArrayList<>(list));
}
for(int i=0;i<num.length;i++){
if(list.contains(num[i])){ //因为这个题没有重复的数字， 所以当list中已经有了这个数字，那就剪枝
continue;
}
list.add(num[i]);
build(num,ans,list);
list.remove(list.size()-1);
}
}
发表于 2023-07-14 15:46:42
回复(2)
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
private ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> current = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
int max = getMax(num);
int[] numCount = new int[max + 1];
for (int idx = 0; idx < num.length; idx++) {
numCount[num[idx]]++;
}
dfs(num, numCount, num.length);
Set<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>(this.all);
this.all.clear();
this.all.addAll(set);
Collections.sort(this.all, new Comparator<ArrayList<Integer>>() {
public int compare(ArrayList<Integer> self, ArrayList<Integer> other) {
int min = Math.min(self.size(), other.size());
for (int idx = 0; idx < min; idx++) {
if (self.get(idx) != other.get(idx)) {
return self.get(idx).compareTo(other.get(idx));
}
}
if (self.size() > other.size()) {
return self.get(min + 1);
} else if (self.size() < other.size()) {
return other.get(min + 1);
}
return 0;
}
});
return this.all;
}
public void dfs(int[] num, int[] numCount, int n) {
if (this.current.size() == n) {
this.all.add((ArrayList<Integer>)this.current.clone());
return;
}
for (int idx = 0; idx < n; idx++) {
int count = getCount(this.current, num[idx]);
if (count < numCount[num[idx]]) {
this.current.add(num[idx]);
dfs(num, numCount, n);
this.current.remove(this.current.size() - 1);
}
}
}
public static int getCount(ArrayList<Integer> list, int num) {
long count = list.stream().filter(item->item == num).collect(
Collectors.counting());
return Long.valueOf(count).intValue();
}
public static int getMax(int[] num) {
int max = Integer.MIN_VALUE;
for (int idx = 0; idx < num.length; idx++) {
if (max < num[idx]) {
max = num[idx];
}
}
return max;
}
}
发表于 2023-05-07 22:23:42
回复(0)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
LinkedList<Integer> temp = new LinkedList<>();
LinkedList<Integer> indexList = new LinkedList<>();
def(result, temp, num, indexList);
return result;
}
public void def(ArrayList<ArrayList<Integer>> result, LinkedList<Integer> temp,
int[] num, LinkedList<Integer> indexList) {
if (indexList.size() == num.length) {
System.out.println(temp);
result.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < num.length; i++) {
if (indexList.contains(i)) {
continue;
}
temp.add(num[i]);
indexList.add(i);
def(result, temp, num, indexList);
indexList.removeLast();
temp.removeLast();
}
}
}
发表于 2023-04-03 11:17:59
回复(0)
import java.util.*;
## 经典回溯
public class Solution {
List<Integer> list = new ArrayList<>();
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
Arrays.sort(num);
dfs(num,list);
return result;
}
private void dfs(int[] num,List<Integer> list){
if(list.size() == num.length){
result.add(new ArrayList<>(list));
return;
}
for(int i = 0; i < num.length; i ++){
if(list.contains(num[i])){
continue;
}
list.add(num[i]);
dfs(num,list);
list.remove(list.size() - 1);
}
}
}
发表于 2023-02-27 17:40:04
回复(1)
力扣第46题
public ArrayList<ArrayList<Integer>> permute (int[] num) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
test(lists,new ArrayList<>(),num);
return lists;
}
public static void test(ArrayList<ArrayList<Integer>> lists, ArrayList<Integer> list, int[] nums) {
if (list.size() == nums.length) {
lists.add(new ArrayList<>(list));
return;
}
for (int i=0;i<nums.length;i++) {
if (list.contains(nums[i])) continue;
list.add(nums[i]);
test(lists,list,nums);
list.remove(list.size()-1);
}
}
发表于 2022-12-03 19:59:45
回复(0)
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<Integer> list = new ArrayList<>();
backTrack(num, list);
return res;
}
public void backTrack(int[] num, ArrayList<Integer> list) {
if (list.size() == num.length) {
res.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < num.length; i++) {
if (list.contains(num[i]))
continue;
list.add(num[i]);
backTrack(num, list);
list.remove(list.size() - 1);
}
}
}
发表于 2022-09-28 17:58:00
回复(1)
知道思路就很简单了
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
boolean[] isUsed = new boolean[num.length];
ArrayList<Integer> list = new ArrayList<>();
Arrays.sort(num);
dfs(num, isUsed, list);
return res;
}
public void dfs(int[] num, boolean[] isUsed, ArrayList<Integer> list) {
if (list.size() == num.length) {
res.add(new ArrayList(list));
}
for (int i = 0; i < num.length; i ++) {
if (isUsed[i] == true) continue;
if (i > 1 && num[i] == num[i - 1]) continue;
list.add(num[i]);
isUsed[i] = true;
dfs(num, isUsed, list);
isUsed[i] = false;
list.remove(list.size() - 1);
}
}
}
发表于 2022-08-09 14:24:42
回复(1)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path=new ArrayList<Integer>();
dfs(num,path,list);
return list;
}
public void dfs(int[] nums,ArrayList<Integer> path,ArrayList<ArrayList<Integer>> list){
if(path.size()==nums.length){
list.add(new ArrayList<Integer>(path));
return;
}
for(int i=0;i<=nums.length-1;i++){
if(path.contains(nums[i])){continue;}
path.add(nums[i]);
dfs(nums,path,list);
path.remove(path.size()-1);
}
}
}
发表于 2022-08-03 16:13:12
回复(0)
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> track = new ArrayList<>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
backtrack(num);
return res;
}
public void backtrack(int[] num){
if(track.size()==num.length) {
res.add(new ArrayList<Integer>(track));
return;
}
for(int i : num){
if(track.contains(i)) continue;
track.add(i);
backtrack(num);
track.remove(track.size()-1);
}
return;
}
}
发表于 2022-07-19 16:06:42
回复(0)
import java.util.*;
public class Solution {
LinkedList<LinkedList> list =
new LinkedList<LinkedList>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
LinkedList<Integer> innerlist = new LinkedList<>();
track(num,innerlist);
// LinkedList 转为ArrayList
ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
ArrayList<Integer> ilist = new ArrayList<>();
for (int j = 0; j < list.get(i).size(); j++) {
ilist.add((Integer)list.get(i).get(j));
}
arrayLists.add(ilist);
}
return arrayLists;
}
public void track(int [] num, LinkedList<Integer> inlist){
return;
}
for (int i = 0; i < num.length; i++) {
if (inlist.contains(num[i])) {
continue;
}
inlist.add(num[i]);
track(num,inlist);
inlist.removeLast();
}
}
}
public class Solution {
LinkedList<LinkedList> list =
new LinkedList<LinkedList>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
LinkedList<Integer> innerlist = new LinkedList<>();
track(num,innerlist);
// LinkedList 转为ArrayList
ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
ArrayList<Integer> ilist = new ArrayList<>();
for (int j = 0; j < list.get(i).size(); j++) {
ilist.add((Integer)list.get(i).get(j));
}
arrayLists.add(ilist);
}
return arrayLists;
}
public void track(int [] num, LinkedList<Integer> inlist){
if (inlist.size()==num.length) {
//这个地方要new
list.add( new LinkedList(inlist));return;
}
for (int i = 0; i < num.length; i++) {
if (inlist.contains(num[i])) {
continue;
}
inlist.add(num[i]);
track(num,inlist);
inlist.removeLast();
}
}
}
发表于 2022-07-17 12:17:05
回复(0)
public class Solution {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
int len;
public ArrayList<ArrayList<Integer>> permute(int[] num) {
if(num==null||num.length==0) return ans;
//先对数组排序保证最后返回的结果是按字典排序输出
Arrays.sort(num);
len = num.length;
//创建一个数组记录已经加入数组的元素
boolean[] isVisi = new boolean[len];
//递归添加元素
dfs(num,isVisi,new ArrayList());
return ans;
}
void dfs(int[] num,boolean[] vis,ArrayList<Integer> ls){
if(ls.size()==len){
ans.add(new ArrayList(ls));
return;
}
for(int i = 0;i<len;i++){
if(vis[i]) continue;
vis[i] = true;
ls.add(num[i]);
dfs(num,vis,ls);
//回溯
vis[i] = false;
ls.remove(ls.size()-1);
}
}
}
发表于 2022-07-16 11:26:21
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-10-16 16:40:21
-
2022-09-23 22:56:40 -
2022-09-20 16:30:28
-
2022-09-16 19:08:49 -
2022-09-16 17:45:14
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
