首页 > 试题广场 >

没有重复项数字的全排列

[编程题]没有重复项数字的全排列

热度指数：85829 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一组数字，返回该组数字的所有排列

例如：

[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 $0 < n \le 6$

要求：空间复杂度 $O(n!)$ ，时间复杂度 $O(n!）$

示例1

输入

[1,2,3]

输出

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

输入

[1]

输出

[[1]]

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > res;
        permutation(res,num,0);
        return res;
    }
    void permutation(vector<vector<int> > &res,vector<int> &num,int s)
    {
    	if(s == num.size()-1)
    		res.push_back(num);
    	else{
    		for(int i=s;i<num.size();i++)
    		{
    			swap(num[s],num[i]);
				permutation(res,num,s+1);
				swap(num[s],num[i]);
			}
		}    		
	}
};

发表于 2017-08-13 06:35:56 回复(7)

JacobGo！

/**
 * 46. Permutations
 * @author Jacob
 * 题意：求数组的全排列
 */
public class Demo1 {
	ArrayList<ArrayList<Integer>> res;

	public ArrayList<ArrayList<Integer>> permute(int[] nums) {
		res = new ArrayList<ArrayList<Integer>>();
		if (nums == null || nums.length < 1)
			return res;
		//对数组元素进行从小到大排序
		Arrays.sort(nums);
		ArrayList<Integer> list = new ArrayList<Integer>();

		solve(list, nums);

		return res;
	}

	private void solve(ArrayList<Integer> list, int[] nums) {
		if (list.size() == nums.length) {
			res.add(new ArrayList<Integer>(list));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if (!list.contains(nums[i])) {
				list.add(nums[i]);
				solve(list, nums);
				list.remove(list.size() - 1);
			}
		}
	}
}

发表于 2017-08-19 10:32:00 回复(11)

Python3

Namely

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # 递归结束条件
        if len(num) <= 1:
            return [num]
        ret = []
        for i, e in enumerate(num):
            r = self.permute(num[:i] + num[i+1:])
            ret += [[e] + k for k in r]
        return ret

发表于 2023-03-02 11:44:56 回复(2)

C/C++

hello古斯卡

是不是应该改下结果判断，如果明确需要结果字典序排列，请在题目处注明，要不就把结果集改成set：

不通过
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为12.50%

用例:
[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,2,1],[3,1,2]]

发表于 2019-11-07 10:15:34 回复(2)

Java

又笨又懒不想上课

排列的时候每次都需要从数组第一个元素开始，所以只需要used数组判断是否使用过，不需要每次递归用start刷新位置。

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> ls = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        int[] used = new int[num.length];
        dfs(num,used);
        return res;
    }
    private void dfs(int[] a,int[] used) {
        if(ls.size() == a.length) {
            res.add(new ArrayList<>(ls));
            return;
        }
        for(int i = 0; i < a.length; i++) {
            if(used[i] == 1) continue;
            used[i] = 1;
            ls.add(a[i]);
            dfs(a,used);
            used[i] = 0;
            ls.remove(ls.size()-1);
        }
    }
}

发表于 2021-06-17 11:01:58 回复(0)

C/C++

卷积神经网络哦

做烂了的回溯

class Solution {
public:
    void dfs(int cur, vector<int> &tmp, vector<int> &taken, vector<int> &num, 
             vector<vector<int> > &res){
        int n = num.size();
        if(tmp.size() == n){res.push_back(tmp);return;}
        for(int i = 0; i < n; i++){
            if(!taken[i]){
                taken[i] = 1;
                tmp.push_back(num[i]);
                dfs(i+1, tmp, taken, num, res);
                tmp.pop_back();
                taken[i] = 0;
            }
        }
    }

    vector<vector<int> > permute(vector<int> &num) {
        vector<int> tmp; 
        vector<int> taken(num.size(), 0);
        vector<vector<int> > res;
        dfs(0, tmp, taken, num, res);
        return res;
    }
};

发表于 2019-07-05 21:05:48 回复(0)

Python3

Vivimore

递归 + 回溯不回溯的话num还停留在上一次递归排列的状态，可能会导致出现漏排的情况
时间复杂度：O(n!) 空间复杂度：O(n) 递归栈的深度
还有注意添加排列好的num时使用深拷贝

import copy
class Solution:
    def recursion(self, num, res, index):
        if index == len(num) - 1:
            res.append(copy.deepcopy(num))
        else:
            for i in range(index, len(num)):
                temp = num[i]
                num[i] = num[index]
                num[index] = temp
                self.recursion(num, res, index+1)
                temp = num[i]
                num[i] = num[index]
                num[index] = temp

    def permute(self , num: List[int]) -> List[List[int]]:
        num.sort()
        res = []
        self.recursion(num, res, 0)
        return res

发表于 2022-05-19 17:35:51 回复(1)

ada_lsj

void swap(int *a, int *b)

{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void dfs(int* num, int index, int numLen, int* returnSize, int** returnColumnSizes, int **ret)
{
int j = 0;
if (index == numLen) {
ret[*returnSize] = (int *)malloc(numLen * sizeof(int));
for (j = 0; j < numLen; j++) {
ret[*returnSize][j] = num[j];
}
(*returnColumnSizes)[*returnSize] = numLen;
(*returnSize)++;
return;
}

for (j = index; j < numLen; j++) {
swap(&num[j], &num[index]);
dfs(num, index+1, numLen, returnSize, returnColumnSizes, ret);
swap(&num[j], &num[index]);
}
return;
}
int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
// write code here
*returnColumnSizes = (int*)malloc(sizeof(int) * 100001);
int **ret = (int**)malloc(sizeof(int*) * 100001);
*returnSize = 0;
dfs(num, 0, numLen, returnSize, returnColumnSizes, ret);

return ret;
}

发表于 2022-05-15 10:41:46 回复(3)

LinuX18

class Solution {
public:
void dfs(vector<int> &num,vector<vector<int>> &res,int begin)
{
    if(begin == num.size())
        res.push_back(num);
    for(int i=begin;i<num.size();i++)
    {
        swap(num[i],num[begin]);
        dfs(num,res,begin+1);
        swap(num[i],num[begin]);
    }
}
vector<vector<int> > permute(vector<int> &num)
{
        vector<vector<int>> res;
        if(num.size()==0)
            return res;
        sort(num.begin(),num.end());
        dfs(num,res,0);
        return res;
}
};

发表于 2017-07-14 15:28:33 回复(0)

Java

-Panda君-

从上图可以看出，当只有到遍历到叶子节点才会得到一个排列结果，因此递归出口是是使用完所有的数字，也就是这个存放排列组合的栈的大小等于数组的长度；

        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)

C++

失败_

递归回溯版本

为什么要发这个呢，看前面的题解，是用交换位置来解决排序问题，说实话我真想不到这种思路

对于这个问题我思维第一反应，就是把子问题看作是n大小的序列排列问题

这样逐步分解到大小为1的vector，这样做的好处就是契合题目要求，最终结果就是按字典排序输出的。

而交换位置的话，是需要另外sort一下的，当然你不sort也能通过，结果不会检查字典顺序

以下是我照此思路递归实现的

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> res;
        vector<int> ans;

        recursion(num, ans, res);
        return res;
    }

    void recursion(vector<int> vec, vector<int> &ans, vector<vector<int>> &res){
        if(vec.size()==1){
            ans.push_back(vec[0]);
            res.push_back(ans);
            ans.pop_back();
            return;
        }

        for(int i : vec){
            ans.push_back(i);
            vector<int> newvec;
            for (int j : vec){
                if(i!=j) newvec.push_back(j);
            }
            recursion(newvec, ans, res);
            ans.pop_back();
        }
    }
};

发表于 2023-03-18 23:48:58 回复(0)

Java

听风起云

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)

C++

Spectre_

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        // 时间复杂度O(N!)，空间复杂度O(N!)
        vector<vector<int>> res;
        vector<int> path;
        sort(num.begin(), num.end());
        recursion(num, path, res);
        return res;
    }
    void recursion(vector<int> &num, vector<int> &path, vector<vector<int>> &res) {
        if (num.empty()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < num.size(); ++i) {
            path.push_back(num[i]);
            vector<int> tmp(num);  // 拷贝一份，删除path中加入的num[i]
            tmp.erase(tmp.begin() + i);
            recursion(tmp, path, res);
            path.pop_back();
        }
    }
};

发表于 2022-10-14 21:29:19 回复(0)

箫声

class Solution {
public:
    void pushVec(vector<int> num, int index){
        per.push_back(num);
        for(int i = index; i < num.size()-1; ++ i){
            for(int j = i+1; j < num.size(); ++ j){
                swap(num[i],num[j]);
                pushVec(num,i+1);
                swap(num[i],num[j]);
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        pushVec(num,0);
        return per;
    }
private:
    vector<vector<int> > per;
};

发表于 2018-02-14 20:16:46 回复(0)

C/C++

꧁Kai

class Solution {
public:
    //next_permutation:会取得[first,last)所标识之序列的下一个排列组合
    //如果没有下一个排列组合，便返回false，否则返回true。
   vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > res;
	sort(num.begin(), num.end());
	do 
	{
		res.push_back(num);
	} while (next_permutation(num.begin(),num.end()));
	return res;
    }
};

编辑于 2016-09-02 18:12:47 回复(2)

C/C++

kakaan

全排列生成么，因为没说输入时字典序，所以不能用next_permutation

所以得自己写全排列

递归，交换i和开头，

class Solution {
    void permutation(vector<vector<int> >&ans,vector<int>& num,int l)
    {
        if(l == num.size()-1)
            ans.push_back(num);
        else
        {
            for(int i=l;i<num.size();i++)
            {
                swap(num[l],num[i]);
                permutation(ans,num,l+1);
                swap(num[l],num[i]);
            }
        }
    }
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > ans;
        permutation(ans,num,0);
        return ans;
    }
};

发表于 2016-09-02 17:18:36 回复(3)

Java

人间水长东

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)

Python3

川流不息憨憨

from itertools import permutations
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        return list(permutations(num, len(num)))

编辑于 2024-03-19 21:40:37 回复(0)

Python3

对角线1

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        res = []
        n = len(num)
        if n <=1 :return [num]
        for i in range(n):
            for item in self.permute(num[:i]+num[i+1:]):
                temp = [num[i]]+item
                res.append(temp)
        return res

发表于 2023-11-13 11:17:23 回复(0)

Java

做则必成的勇气和信心

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)