dfs

 avatar
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