5 5 votes
Article Rating
Subscribe
提醒
guest
4 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
暴走的楚狂
# Python
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return permutations(nums)
    
    def permutations(nums, trace=[]):
        if len(nums) <= 1:
            return [nums + trace]
        result = []
        for i, num in enumerate(nums):
            result += permutations(nums[:i] + nums[i + 1 :], trace + [num])
        return result

gh_BMDACMER

// 采用深度优先遍历dfs
/**
* 思路:类似于二叉树,第一层为空数组[] 第二层分别由1 2 3 …元素组成 之后第三层。。。直到遍历到叶子节点
* 将第一层depth=0 则最后一层即为数组长度 这是终止条件 之后就是回溯了
* @param nums
* @return
*/
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) return res;
LinkedList<Integer> path = new LinkedList<>();
boolean[] used = new boolean[len];
dfs(nums, len, 0, used, path, res);
return res;
}

private void dfs(int[] nums, int len, int depth, boolean[] used, LinkedList<Integer> path, List<List<Integer>> res) {
if (len == depth) {
res.add(new ArrayList<>(path));
return;
}

for (int i = 0; i < len; i++) {
if (used[i]) {
continue;
}
path.addLast(nums[i]);
used[i] = true;
dfs(nums, len, depth + 1, used, path, res);
path.removeLast();
used[i] = false;
}
}

水木黄昏

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

public void backtrack(List<List> res, List list, int[] nums) {
if(list.size() == nums.length) {
res.add(new ArrayList(list));
return;
}
for(int num : nums) {
if(!list.contains(num)) {
list.add(num);
backtrack(res, list, nums);
list.remove(list.size() – 1);
}
}
}
}
//都是回溯

Hao
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.ans = []
        
        def backtrack(cur, total):
            if not total:
                self.ans.append(cur[:])
                return
            
            for i in range(len(total)):
                cur.append(total[i])
                backtrack(cur, total[:i] + total[i+1:])
                cur.pop(-1)
        
        backtrack([], nums)
        return self.ans

经典回溯算法