Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers via Depth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a positive integer n, return whether n can be written as the sum of distinct positive factorial numbers.

Example 1
Input
n = 31
Output
True
Explanation
Since 31 = 4! + 3! + 1!

Example 2
Input
n = 4
Output
False
Explanation
Since 4 = 2! + 2! but not distinct.

Example 3
Input
n = 6
Output
True
Example 4
Input
n = 29
Output
False

Hints:
Can we generate all factorials up to n?
super increasing sequence knapsack

Sum of Distinct Positive Factorial Numbers via Depth First Search Algorithm

We generate all the factorial numbers (distinct) that are smaller than n – and the question becomes to pick a subset of these numbers (for each factorial number, we can choose to pick 1 or not pick). Then the question becomes one of the Knapsack problem.

We can use Depth first search algorithm to search for a possibility. Each item we can choose to pick or skip until the n is reduced to zero or negative, or we have run out of the items. The time complexity is O(2^M) where M is the number of the factorials that are smaller than n.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def factorialSum(self, n):
        fact = x = 1
        res = deque()
        while fact <= n:
            fact *= x
            res.appendleft(fact)
            x += 1
        def dfs(l, n):
            if n == 0:
                return True
            if n < 0:
                return False
            if l == len(res):
                return False
            return dfs(l + 1, n - res[l]) or dfs(l + 1, n)
        return dfs(0, n)

class Solution:
    def factorialSum(self, n):
        fact = x = 1
        res = deque()
        while fact <= n:
            fact *= x
            res.appendleft(fact)
            x += 1
        def dfs(l, n):
            if n == 0:
                return True
            if n < 0:
                return False
            if l == len(res):
                return False
            return dfs(l + 1, n - res[l]) or dfs(l + 1, n)
        return dfs(0, n)

Therefore, this approach is less efficient than the greedy O(M) solution we talked about yesterday: Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers

Sum of Distinct Positive Factorial Numbers:

• Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers
• Algorithms to Sum using Distinct Positive Factorial Numbers
• Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers via Depth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —