dfs
user_8886827
python
a month ago
1.3 kB
1
Indexable
Never
def find_combinations(n): nums = [i for i in range(5, n+5, 5)] result = [] stack = [((), 0)] # (current_comb, start_index) min_size = float('inf') def powerset(comb): result = [[]] for element in comb: new_subsets = [] for subset in result: new_subsets.append(subset + [element]) result.extend(new_subsets) return result def is_comb_valid(comb, n): for num in nums: can_form = False for subset in powerset(comb): if sum(subset) == num: can_form = True break if not can_form: return False return True while stack: comb, start = stack.pop() #print(comb) if is_comb_valid(comb, n): if len(comb) < min_size: result = [list(comb)] min_size = len(comb) elif len(comb) == min_size: result.append(list(comb)) continue if len(comb) >= min_size: continue for i in range(start, len(nums)): new_comb = comb + (nums[i],) if sum(new_comb) <= n: stack.append((new_comb, i)) return result n = 25 print(f"For {n} = {find_combinations(n)}")
Leave a Comment