arrays - Subset Sum Problem [Nested Loop Solution?]

Question

I am working on to solve the Subset - Sum problem. Problem statement is-

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Example: Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9 Output: True //There is a subset (4, 5) with sum 9.

I have seen different approaches to solve this problem. One of them is using recursion and other one is using Dynamic Programming.

My Question is, Why cant we solve the problem using nested loops. Each one of them considering an element and checking it one by one whether it makes a complete sum or not?

Sorry, I am new to algorithms and stuff.

标签： arraysalgorithmdynamic-programmingsubset-sum

Answer 1

It is actually possible to solve the subset sum problem with (a lot) of nested loops. That would probably be referred to as the "non-recursive brute force naive approach", or something.
You probably will never see it, because it is a very, very, ..., very clumsy way to tackle the problem.
Indeed, you would need as many nested loops as you have elements in your input set, which would mean writing a different program for each case (1 element in your starting set, 2 elements in your starting set, etc etc ...).
Or eventually, writing a program that takes a set size N as input, and writes a program with N nested loops. But the result, in any case, would be as far of "good coding practices" as it can be.

The recursive approach does exactly that (it is strictly equivalent to a lot of nested loops, each recursive call send you in a 'new' loop), but much more simply and elegantly (despite doing a complete enumeration of subsets of a set, which is very, very costly). A simpler code is easier to check, easier to edit, easier to test, easier to debug ... (and on and on .... good practices are often here for a reason).