Algorithm/집합 & 순열과 조합5 [leetcode] subset subset 한 집합이 주어질때 모든 부분집합을 리턴 solution1 itertools 의 combinations 이용 0 ~ len(nums) 크기의 조합 찾아서 결과값에 추가 code1 from itertools import combinations class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ # nCr 에서 r = 0 , r = len(nums) 일때 result = [[],nums] # r = 1 ~ len(nums)-1 일때 for i in range(1,len(nums)): result.extend(list(map(list,combinations(nums,.. 2022. 1. 17. [leetcode] combination sum combination sum 숫자 집합(candidates)과, target 숫자가 주어진다 숫자 집합의 숫자를 조합해서 target이 되는 모든 경우를 나열 숫자 집합의 원소를 여러번 사용할수 있다 solution dfs를 통해서 작은 원소부터 cur에 하나씩 추가 target에 도달하면 결과값에 포함 target을 초과하는 경우에는 탐색 종료 한 원소를 추가하면 다음 재귀 에서는 그 원소보다 작은 원소는 추가할수 없게 한다 code class Solution(object): def combinationSum(self, candidates, target): candidates = sorted(filter(lambda x : x target : break cur.append(el) dfs(cur,elem.. 2022. 1. 17. [leetcode] combinations combinations n, k ( n >= k >= 1) 의 정수가 주어질때 n 개의 정수 (1 ~ n) 에서 k 개의 수를 뽑는 조합을 리턴 Solution1 itertools의 combinations 이용 code1 from itertools import combinations class Solution(object): def combine(self, n, k): return list(map(list,combinations(range(1,n+1),k))) Solution2 dfs(selected:list,start:int) selected에 el 이 추가된 경우 다음의 dfs에서 start = el + 1 종료조건 len(selected) == k code2 class Solution(object).. 2022. 1. 13. [leetcode] permutations permutations 서로다른 숫자로 구성된 배열을 입력으로 받는다 가능한 모든 조합의 순열을 리턴 Solution1 itertools의 permutations를 사용 code1 from itertools import permutations class Solution(object): def permute(self, nums): return list(map(list,permutations(nums))) Solution2 next_permutation(nums)메서드 구현 nums[i-1] < nums[i] 인 가장 큰 i 찾기 nums[i:] 범위에서 nums[i-1] < nums[j] 인 가장큰 j 찾기 nums[i-1] 와 nums[j] 를 swap nums[i:] 를 양 끝에서 가운데 방향으로 sw.. 2022. 1. 13. 이전 1 2 다음