[Leetcode 46] - Permutations w/ Python

 

 

Given an array nums of distinct integers, return all the possible permutations. 

You can return the answer in any order.

 

 

 

배열이 주어졌을때 순열을 찾는 문제

 

 

 

https://leetcode.com/problems/permutations/description/

 

 

---

 

 

 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

 

 

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

 

 

 

Example 3:

Input: nums = [1]
Output: [[1]]

 

 

 

---

 

 

답은 매우 쉽죠?

 

class Solution:
    def permute(self, nums):
        n = list(permutations(nums))
        return n

 

 

그럼 다음 포스트로 넘어가...

 

 

---

 

 

 

고 싶지만

 

 

Permutation, Combination 문제가 나오면 itertools

없이도 푸는 연습하는게 중요한것 같다

 

 

 

Backtracking을 통해 문제를 풀었다

1. Nums의 길이 만큼 확인을 한다면 현재 보는 숫자가 stack에 들어있으면 continue 아니라면 추가

2. 이를 통해 모든 숫자의 Permutation을 확인하고 길이가 nums만큼 될때마다 ans에 추가

 

 

class Solution:
    def permute(self, nums):
        curr = []
        ans = []

        def backtrack():
            if len(curr) == len(nums):
                ans.append(list(curr))
            else:
                for i in range(len(nums)):
                    if nums[i] in curr:
                        continue
                    curr.append(nums[i])
                    backtrack()
                    curr.pop()
        backtrack()
        return ans