Subset Sum : Why is DFS + pruning faster than 2 for loop?
<p>This issue is leetcode 416 Partition Equal Subset Sum.</p>

<pre><code>#2 for loop, which got TLE
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums.sort()
        allsum = sum(nums)
        if allsum % 2 == 1:
            return False
        subsets = {() : 0}
        temp = dict(subsets)
        for each in nums:
            for subset in subsets:
                new = temp[subset] + each
                if new * 2 == allsum:
                    return True
                elif new * 2 &lt; allsum:
                    temp[tuple(list(subset) + [each])] = new
                else:
                    del temp[subset]
            subsets = dict(temp)
        return False

DFS + pruning:
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums.sort()
        if sum(nums) % 2 != 0:
            return False
        else:
            target = sum(nums) / 2
        return self.path(nums, len(nums), target)

def path(self, nums, length, target):#DFS + pruning
    if target == 0:
        return True
    elif target &lt; 0 or (target &gt; 0 and length == 0):
        return False
    if self.path(nums, length - 1, target - nums[length - 1]):
        return True
    return self.path(nums, length - 1, target)
</code></pre>

<p>Why is 2 for loop slower than DFS? They both have pruning, and I think the time complexity of DFS, which is a np problem, should be worse than 2 for loop, isn't it?</p>

<p>Just because you are using two loops it doesn't mean that your algorithm is in <em>O(n<sup>2</sup>)</em> or polynomial. The complexity of the algorithm depends on how many times each loop executes.
In this part of code:</p>

<pre><code>    for each in nums:
        for subset in subsets:
            ....
</code></pre>

<p>The first loop will run <em>n</em> times because the size of <code>nums</code> is <em>n</em> and it doesn't change. However size of <code>subsets</code> is getting 2 times larger after each iteration. So the body of your second <code>for</code> loop will executes <code>1 + 2 + 4 + 8 + 16 + 32 + ... + 2^n = 2^(n+1)</code> times.</p>

<p>So your algorithm is in <em>O(2<sup>n</sup>)</em> without even considering the costly operations (copying <code>list</code>s and <code>dict</code>s) you perform in the body of the second loop.</p>

<p>Your second method (Which is not technically a DFS) is equivalent to your first method in the case complexity. They both are <em>O(n<sup>2</sup>)</em>. But in the second method you do less extra work in comparison to your first method (copying <code>list</code>s and <code>dict</code>s, etc). So your first method will might run faster but it doesn't matter in the long run. Both of this methods won't be efficient enough for a bigger size of input.</p>

<p>Note that this is a very famous problem called <a href="https://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">Subset-sum</a> which is NP-Complete. It can be solved using <a href="http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/" rel="nofollow">Dynamic Programming</a> in <a href="https://en.wikipedia.org/wiki/Pseudo-polynomial_time" rel="nofollow">Pseudo-polynomial time</a>.</p>

python algorithm loops recursion time-complexity