LeetCode 47(Permutations II, Python)

1. 문제 링크 

• https://leetcode.com/problems/permutations-ii

Permutations II - LeetCode

 

2. 문제 설명

• 이전 46. Permutations와 유사하게, nums라는 array가 주어졌을 때, 모든 가능한 조합을 반환하는 것.
  • 단, 이전문제에서는 nums내의 integer가 'unique'했다면, 이번엔 중복이 허용되는 차이가 있음
• 예시1)
  • nums=[1,1,2] 라면 [[1,1,2], [1,2,1], [2,1,1]]을 반환
• 예시2) → Permutations에 나온 예시
  • nums=[1,2,3]이라면, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]을 반환 

3. 기존 풀이

• combination sum II와 유사하게 접근을 했다.
  • 우선 nums에서 각 element가 몇 번 등장했는지에 대한 dictionary를 만들고, 
  • nums를 set을 활용하여 중복을 제외한 리스트로 만든 뒤,
  • backtracker 함수를 실행하는데,
    
    • 기존과 동일하게, len(path)와 기존의 nums길이가 동일하면 output.append를 시키고, 
    • 그렇지 않은 경우는, 
      • (permutation 1과 다른 부분) path에 있는 i의 개수와, 최대로 들어갈 수 있는 i의 숫자에 대한 대소비교를 하여, 최대 들어갈 수 있는 i 개수보다 작다면, path를 append하고 → backtracker를 실행하고 → path를 다시 pop하는 구조로 짜두었다
• runtime은 80%로 나쁘지 않은데, memory가 dict을 저장하는 부분이 있어서 그런지 낮은 편이었음

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        
        nums_dict = {}
        for i in nums:
            if i not in nums_dict:
                nums_dict[i] = 1
            else:
                nums_dict[i] +=1

        len_nums= len(nums)

        def backtracker(path): 
            if len(path) == len_nums:
                output.append(path.copy())
                return 
            else:
                for i in nums: 
                    if nums_dict[i] > path.count(i):
                        path.append(i)
                        backtracker(path)
                        path.pop()


        output = []
        nums = list(set(nums))
        backtracker([])

        return output

 

4. 다른 풀이

• 리트코드에서 runtime이 높았던 다른 사람의 풀이 
  • 기본 backtracker 구조는 유사하나, 
    • used = [False]*len(nums)로 만들어서,
    • used[i]가True거나, (이미 사용했거나), nums[i]==nums[i-1]인데 used[i]가 False면 그 다음 for문 루프로 가고,
    • 그렇지 않으면, used[i]를 True로 바꾼뒤 backtrack을 한 뒤, 다시 원복(path.pop(), used[i] =False)하는 구조

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(path,used):
            if len(path)==len(nums):
                res.append(path[:])
                return 
            for i in range(len(nums)):
                if used[i] or (i>0 and nums[i]==nums[i-1] and not used[i-1]):
                    continue
                used[i] = True 
                path.append(nums[i]) #append and add to used 
                backtrack(path,used)
                path.pop()
                used[i] = False

        res = []
        nums.sort()
        used = [False]*len(nums)
        backtrack([],used)
        return res

 

• 아래 풀이의 경우
  • nums[i] == nums[i-1] 이면 continue하고, 
  • 그렇지 않으면, nums[i]를 제외한 것을 인자로 넘겨주고, nums[i]는 현재 path에 추가해주는 구조로 작성
    • dfs(nums[:i]+nums[i+1:], curr+nums[i]],ans) 이부분 

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        self.dfs(nums, [], ans)  
        return ans

    def dfs(self, nums, curr, ans):
        if not nums:
            ans.append(curr)
            return
        for i in range(len(nums)):
            if i == 0:
                self.dfs(nums[1:], curr+[nums[i]], ans)
            else:
                if nums[i] == nums[i-1]:
                    continue
                self.dfs(nums[:i]+nums[i+1:], curr+[nums[i]], ans)

 

5. 배운 점

• backtracking가 약간씩 헷갈리는데, 별도로 정리해둘 필요가 있겠다.