найти все подмножества, сумма которых равна x, используя начальный код

Я не очень хорошо объясняю, но я думаю, что более естественным способом было бы написать это так:

// Algorithm stops once k is the least element in the array
if (k == 0) {
    if (sum == 0 || sum == arr[k]) {
        // Either we can sum to "sum"
        return 1;
    }
    else {
        // Or we can't sum to "sum"
        return 0;
    }   
}   

// Otherwise, let's recursively see if we can sum to "sum"

// Any valid subset either includes arr[k]
return countSubsetSum2(arr, k-1, sum - arr[k]) +
// Or it doesn't
countSubsetSum2(arr, k-1, sum);

Как описано выше, эта функция принимает входные данные и выводит значение, которое мы можем определить и доказать как истинное математически (предупреждение: обычно это не совсем доказательство, потому что крайние случаи в большинстве языков программирования, к сожалению).

В любом случае, чтобы вернуться к вашему вопросу. Проблема с приведенным выше кодом заключается в том, что он не хранит никаких данных... он просто возвращает счетчик. Вместо этого давайте сгенерируем фактические подмножества, пока мы их генерируем. В частности, когда я говорю Any valid subset either includes arr[k], я имею в виду... генерируемое нами подмножество включает arr[k]; так добавь. Ниже я предположил, что код, который вы написали выше, является java-ish. Надеюсь, это имеет смысл:

// Algorithm stops once k is the least element in the array
if (k == 0) {
    if (sum == 0 || sum == arr[k]) {
        // Either we can sum to "sum" using just arr[0]
        // So return a list of all of the subsets that sum to "sum"
        // There are actually a few edge cases here, so we need to be careful
        List<Set<int>> ret = new List<Set<int>>();

        // First consider if the singleton containing arr[k] could equal sum 
        if (sum == arr[k])
        {   
            Set<int> subSet = new Subset<int>();
            subSet.Add(arr[k]);
            ret.Add(subSet);
        }   

        // Now consider the empty set 
        if (sum == 0)
        {   
            Set<int> subSet = new Subset<int>();
            ret.Add(subSet);
        }   

        return ret;
    }   
    else {
        // Or we can't sum to "sum" using just arr[0]
        // So return a list of all of the subsets that sum to "sum". None 
        // (given our inputs!)
        List<Set<int>> ret = new List<Set<int>>();
        return ret;
    }
}

// Otherwise, let's recursively generate subsets summing to "sum"

// Any valid subset either includes arr[k]
List<Set<int>> subsetsThatNeedKthElement = genSubsetSum(arr, k-1, sum - arr[k]);
// Or it doesn't
List<Set<int>> completeSubsets = genSubsetSum(arr, k-1, sum);

// Note that subsetsThatNeedKthElement only sum to "sum" - arr[k]... so we need to add
// arr[k] to each of those subsets to create subsets which sum to "sum"
// On the other hand, completeSubsets contains subsets which already sum to "sum"
// so they're "complete"

// Initialize it with the completed subsets
List<Set<int>> ret = new List<Set<int>>(completeSubsets);
// Now augment the incomplete subsets and add them to the final list
foreach (Set<int> subset in subsetsThatNeedKthElement)
{
    subset.Add(arr[k]);
    ret.Add(subset);
}

return ret;

Код довольно загроможден всеми комментариями; но ключевым моментом является то, что эта реализация всегда возвращает то, что указано для возврата (список наборов целых чисел от arr[0] до arr[k], сумма которых равна любой переданной сумме).

К вашему сведению, есть еще один подход "снизу вверх" (т.е. не использующий рекурсию), который должен быть более производительным. Если вы реализуете это таким образом, вам нужно хранить дополнительные данные в статическом состоянии («запоминаемая таблица»)... что немного некрасиво, но практично. Однако, когда вы реализуете это таким образом, вам нужен более умный способ создания подмножеств. Не стесняйтесь задавать этот вопрос в отдельном посте после того, как попробуете.