Вернуть элементы массива в задаче суммы подмножеств

Question

Для следующего рекурсивного решения проблемы суммы подмножеств ( см. Эту ссылку ) следующий код возвращает значение true, если в a есть какое-либо подмножество, сумма которого равна значению sum

def isSubsetSum(set,n, sum) : 

    # Base Cases 
    if (sum == 0) : 
        return True
    if (n == 0 and sum != 0) : 
        return False

    # If last element is greater than sum, then ignore it 
    if (set[n - 1] > sum) : 
        return isSubsetSum(set, n - 1, sum); 

    # else, check if sum can be obtained by any of the following 
    # (a) including the last element 
    # (b) excluding the last element    
    return isSubsetSum(set, n-1, sum) or isSubsetSum(set, n-1, sum-set[n-1]) 

set = [2, 1, 14, 12, 15, 2] 
sum = 9
n = len(set) 
if (isSubsetSum(set, n, sum) == True) : 
    print("Found a subset with given sum") 
else : 
    print("No subset with given sum") 

Как я могу также вернуть индексы a, которые удовлетворяют sum?

Кроме того, как я могу заставить функцию работать для отрицательных целых чисел в массиве a.

Answer 1

Это одна из возможностей:

def isSubsetSum(numbers, n, x, indices):
    # Base Cases
    if (x == 0):
        return True
    if (n == 0 and x != 0):
        return False
    # If last element is greater than x, then ignore it
    if (numbers[n - 1] > x):
        return isSubsetSum(numbers, n - 1, x, indices)
    # else, check if x can be obtained by any of the following
    # (a) including the last element
    found = isSubsetSum(numbers, n - 1, x, indices)
    if found: return True
    # (b) excluding the last element
    indices.insert(0, n - 1)
    found = isSubsetSum(numbers, n - 1, x - numbers[n - 1], indices)
    if not found: indices.pop(0)
    return found

numbers = [2, 1, 4, 12, 15, 3]
x = 9
n = len(numbers)
indices = []
found = isSubsetSum(numbers, n, x, indices)
print(found)
# True
print(indices)
# [0, 2, 5]

РЕДАКТИРОВАТЬ: для более чистого интерфейса вы можете заключить предыдущую функцию в другую, которая возвращает список индексов при успехе, и None в противном случае:

def isSubsetSum(numbers, x):
    indices = []
    found = _isSubsetSum_rec(numbers, len(numbers), x, indices)
    return indices if found else None

def _isSubsetSum_rec(numbers, n, x, indices):
    # Previous function

Answer 2

Вот подход: вместо True и False мы возвращаем подмассив, если найден, иначе None:

def isSubsetSum(sset,n, ssum) : 

    # Base Cases 
    if (ssum == 0) : 
        return []
    # not found
    if (n == 0 and ssum != 0) : 
        return None

    # If last element is greater than sum, then ignore it 
    if (sset[n - 1] > ssum) : 
        return isSubsetSum(sset, n - 1, ssum); 

    # else, check if sum can be obtained by any of the following 
    # (a) including the last element 
    # (b) excluding the last element    
    a1 = isSubsetSum(sset, n-1, ssum)

    # (b) excluding last element fails
    if a1 is None:
        a2 = isSubsetSum(sset, n-1, ssum-sset[n-1])

        # (a) including last element fails
        if a2 is None:
            return None

        # (a) including last element successes
        else: return a2 + [sset[n-1]]
    else:
        return a1


sset = [2, 1, 4, 12, 15, 2] 
ssum = 9
n = len(sset) 
subset = isSubsetSum(sset, n, ssum) 
if subset is not None : 
    print(subset) 
else : 
    print("No subset with given sum") 

# [2, 1, 4, 2]

Answer 3

Самый простой способ - сделать список индексов еще одним параметром функции. Поддерживайте его при перемещении вниз по дереву вызовов.

«Чистый» способ - построить его, вернув назад вверх по дереву с успешным результатом. Вместо того, чтобы возвращать логическое значение, верните список индексов;None указывает на сбой.

Одно важное замечание: не не"затеняйте" встроенный тип с именем переменной;set опасен, поскольку имя переменной и вводят в заблуждение. Попробуйте, например, coins.

Базовые случаи:

if (sum == 0) : 
    return [n]
if (n == 0 and sum != 0) : 
    return None

Рекурсия:

include = isSubsetSum(coins, n-1, sum-coins[n-1]):
if include:
    return include.append(n-1)

Это немедленные добавления для существующего кода. Я настоятельно рекомендую вам изучить эту проблему в режиме онлайн, чтобы увидеть, как ее решили другие. Вы тратите пространство и время, передавая весь список и указатель в качестве параметров;скорее, вы можете начать с последнего элемента и вернуться обратно, обрезая конец списка при каждом вызове. Это значительно упростит ваши проблемы с индексацией.