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))