[leetcode] 3-14회차

https://leetcode.com/problems/permutations/?envType=study-plan-v2&envId=top-interview-150

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        q = collections.deque()
        for num in (nums):
            q.append(([num], 1))
        
        while q:
            permu, cnt = q.popleft()

            if cnt == len(nums):
                ans.append(permu)
                continue
            for num in nums:
                if num not in permu:
                    tmp = permu + [num]
                    q.append((tmp, cnt+1))

        return ans

 

 

https://leetcode.com/problems/combination-sum/?envType=study-plan-v2&envId=top-interview-150

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        ans = []
        q= collections.deque()
        n = len(candidates)
        for i in range(n):
            candidate = candidates[i]
            if candidate < target:
                q.append(([candidate], i)) # (arrays, idx)
            if candidate == target:
                ans.append([candidate])
        while q:
            combi, cur_idx = q.popleft()
            sum_combi = sum(combi)
            for i in range(cur_idx, n):
                if sum_combi + candidates[i] < target:
                    q.append((combi + [candidates[i]], i))
                elif sum_combi + candidates[i] == target:
                    ans.append(combi + [candidates[i]])
                else:
                    break
            

        return ans

재귀를 쓰지 않고 푸니 꽤나 재밌었다.