46. Permutations

输出一个没有重复数字的数组的全排列

思路： dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 6 star, dfs， 要熟练
        rs = []
        self.dfs(nums, [], rs)
        return rs

    def dfs(self, nums, path, rs):
        if nums == []:
            rs.append(path)
        for i in range(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], rs)

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// todo,  6 star, 这个解答速度太慢，一千五百多毫秒
func permute(nums []int) [][]int {
	if len(nums) == 0 {return [][]int{}}
	result := &[][]int{}
	dfs(nums, []int{}, result)
	return *result

}


func dfs(nums []int, path []int, result *[][]int)  {
	fmt.Println(nums, path, *result)
	if len(nums) == 0 {
		tempPath := make([]int, len(path))
		copy(tempPath, path)
		*result = append(*result, path)
		return
	}
	for i, num := range nums {
		left := make([]int, len(nums))
		copy(left, nums)
		left = append(left[:i], left[i+1:]...)
		dfs(left, append(path, num), result)

		//dfs(append(nums[:i], nums[i+1:]...), append(path, num), result)   一开始这样写，但结果不对，
	}
}