sum of subset pro

Complexity: The time complexity of the dynamic programming solution is �(�⋅�)O(n⋅X), where �n is the number of elements in the set �S, and �X is the target sum. This makes the Subset Sum Problem pseudo-polynomial, meaning the time complexity is polynomial in the numeric value of the input.

In general, the Subset Sum Problem is considered a challenging problem, and while dynamic programming provides a solution, the problem remains NP-complete, implying that there is no known polynomial-time algorithm for it unless P equals NP (which is an open question in computer science).

Certainly! Here's a simple algorithm for the Subset Sum Problem using the backtracking method:

plaintextCopy code
Algorithm: SubsetSumBacktrack

Input:
  - arr: Array of positive integers
  - n: Size of the array
  - target: Target sum
  - subset: Current subset being considered (initially empty)
  - currentSum: Current sum of elements in the subset (initially 0)

Output:
  - Print subsets with the sum equal to the target

Procedure:
1. If currentSum is equal to the target, print the current subset and return.
2. If the currentSum exceeds the target or we have processed all elements in the array, return.

   For each remaining element in the array:
3.   Include the current element in the subset.
4.   Recursively call SubsetSumBacktrack with the updated subset, currentSum, and the remaining elements.
5.   Exclude the current element from the subset.
6.   Recursively call SubsetSumBacktrack with the original subset, currentSum, and the remaining elements.

Example Usage:
   Call SubsetSumBacktrack(arr, n, target, [], 0) where 'arr' is the array of positive integers, 'n' is the size of the array, and 'target' is the desired sum.

Backtracking subset sum

In Backtracking algorithm as we go down along depth of tree we add elements so far, and if the added sum is satisfying explicit constraints, we will continue to generate child nodes further. Whenever the constraints are not met, we stop further generation of sub-trees of that node, and backtrack to previous node to explore the nodes not yet explored.We need to explore the nodes along the breadth and depth of the tree. Generating nodes along breadth is controlled by loop and nodes along the depth are generated using recursion (post order traversal).

Steps:

1. Start with an empty set
2. Add the next element from the list to the set
3. If the subset is having sum M, then stop with that subset as solution.
4. If the subset is not feasible or if we have reached the end of the set, then backtrack through the subset until we find the most suitable value.
5. If the subset is feasible (sum of seubset < M) then go to step 2.
6. If we have visited all the elements without finding a suitable subset and if no backtracking is possible then stop without solution.

Pseudocode

void subset_sum(int list[], int sum, int starting_index, int target_sum)
{
        if( target_sum == sum )
        {
            subset_count++;
            if(starting_index < list.length)
                subset_sum(list, sum - list[starting_index-1], starting_index, target_sum);
        }
        else
        {
            for( int i = starting_index; i < list.length; i++ )
            {
                subset_sum(list, sum + list[i], i + 1, target_sum);
            }
        }
    }