Attempts to find a subset of numbers that sums exactly to a target value using a greedy strategy.

# Subset Sum - Greedy Approach (Not Guaranteed Optimal) # Description: Attempts to find a subset of numbers that sums exactly to a target value using a greedy strategy. def subset_sum(nums, target): """ Find a subset of numbers that sum exactly to the target using a greedy approach. This algorithm attempts to construct a subset by selecting numbers in a way that approaches the target sum. It is not guaranteed to find a solution even if one exists, due to its greedy nature. Args: nums (list of int): List of available numbers to select from. target (int): The desired total sum. Returns: list or str: A subset that sums to the target, or "No solution" if not found. Key Characteristics: - Sorts numbers in descending order to prioritize larger numbers - Greedily selects numbers that don't exceed the target - Not guaranteed to find a solution for all possible inputs Time Complexity: O(n log n) due to sorting Space Complexity: O(n) Note: This is an approximation and may not work for all subset sum instances. """ # Check for invalid or impossible inputs if target < 0 or not nums: return "No solution" # Sort numbers in descending order to prioritize larger numbers sorted_nums = sorted(nums, reverse=True) # Attempt to construct a subset current_subset = [] current_sum = 0 # Greedily select numbers that don't exceed the target for num in sorted_nums: # If adding the current number doesn't exceed the target, include it if current_sum + num target or index >= len(nums): return None # Try including the current number with_current = backtrack( index + 1, current_subset + [nums[index]], current_sum + nums[index] ) if with_current: return with_current # Try excluding the current number without_current = backtrack( index + 1, current_subset, current_sum ) return without_current result = backtrack(0, [], 0) return result if result else "No solution" # Demonstration function def demonstrate_subset_sum(): """ Demonstrate subset sum solving with various inputs. """ test_cases = [ ([1, 2, 3, 4, 5, 6], 10), # Possible solution ([7, 3, 2, 5], 15), # Another test case ([100, 200, 300], 50) # Impossible case ] for nums, target in test_cases: print(f"\nTesting nums={nums}, target={target}") print("Greedy Approach:", subset_sum(nums, target)) print("Advanced Approach:", subset_sum_advanced(nums, target))

Mar 28, 2025 - 04:49

Attempts to find a subset of numbers that sums exactly to a target value using a greedy strategy.

# Subset Sum - Greedy Approach (Not Guaranteed Optimal)
# Description: Attempts to find a subset of numbers that sums exactly to a target value using a greedy strategy.

def subset_sum(nums, target):
    """
    Find a subset of numbers that sum exactly to the target using a greedy approach.

    This algorithm attempts to construct a subset by selecting numbers 
    in a way that approaches the target sum. It is not guaranteed to find 
    a solution even if one exists, due to its greedy nature.

    Args:
        nums (list of int): List of available numbers to select from.
        target (int): The desired total sum.

    Returns:
        list or str: A subset that sums to the target, or "No solution" if not found.

    Key Characteristics:
    - Sorts numbers in descending order to prioritize larger numbers
    - Greedily selects numbers that don't exceed the target
    - Not guaranteed to find a solution for all possible inputs

    Time Complexity: O(n log n) due to sorting
    Space Complexity: O(n)

    Note: This is an approximation and may not work for all subset sum instances.
    """
    # Check for invalid or impossible inputs
    if target < 0 or not nums:
        return "No solution"

    # Sort numbers in descending order to prioritize larger numbers
    sorted_nums = sorted(nums, reverse=True)

    # Attempt to construct a subset
    current_subset = []
    current_sum = 0

    # Greedily select numbers that don't exceed the target
    for num in sorted_nums:
        # If adding the current number doesn't exceed the target, include it
        if current_sum + num <= target:
            current_subset.append(num)
            current_sum += num

        # Early exit if exact target is reached
        if current_sum == target:
            return current_subset

    # Check if an exact solution was found
    return current_subset if current_sum == target else "No solution"

# Alternative implementation demonstrating multiple approaches
def subset_sum_advanced(nums, target):
    """
    A more comprehensive subset sum solver with multiple strategies.

    This version demonstrates additional handling and can be extended 
    to include more sophisticated search strategies.

    Args:
        nums (list of int): List of available numbers.
        target (int): Desired total sum.

    Returns:
        list or str: Solutions found through different methods.
    """
    def backtrack(index, current_subset, current_sum):
        # Found a valid subset
        if current_sum == target:
            return current_subset

        # Exceeded target or reached end of numbers
        if current_sum > target or index >= len(nums):
            return None

        # Try including the current number
        with_current = backtrack(
            index + 1, 
            current_subset + [nums[index]], 
            current_sum + nums[index]
        )
        if with_current:
            return with_current

        # Try excluding the current number
        without_current = backtrack(
            index + 1, 
            current_subset, 
            current_sum
        )
        return without_current

    result = backtrack(0, [], 0)    
    return result if result else "No solution"

# Demonstration function
def demonstrate_subset_sum():
    """
    Demonstrate subset sum solving with various inputs.
    """
    test_cases = [
        ([1, 2, 3, 4, 5, 6], 10),   # Possible solution
        ([7, 3, 2, 5], 15),          # Another test case
        ([100, 200, 300], 50)        # Impossible case
    ]

    for nums, target in test_cases:
        print(f"\nTesting nums={nums}, target={target}")
        print("Greedy Approach:", subset_sum(nums, target))
        print("Advanced Approach:", subset_sum_advanced(nums, target))