алгоритм получения подмножества массива с целевой суммой не работает

Ваше решение неверно, потому что это жадный подход. Он решает, следует ли вам добавлять число или нет, основываясь на том факте, что его добавление не нарушает сумму в данный момент.

Однако этот жадный подход не работает на простом примере следующего массива: [1,9,6,5] и с sum=11.

Обратите внимание, что для любого элемента, который вы выберете во внешнем цикле, вы добавите 1 к текущему набору. Но это лишит вас возможности получить сумму 5+6.
Как только вы выберете 5, вы начнете добавлять число, начиная с «1», и добавлять его. Как только он будет добавлен - вы никогда не получите правильное решение.

Также обратите внимание: ваш подход с двойным циклом может генерировать не более O(n^2) разных подмножеств, но может быть экспоненциальное количество подмножеств, поэтому что-то должно быть не так.

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

На каждом шаге «угадывайте», есть ли текущий элемент в наборе или нет, и рекурсивно выполняйте оба варианта для меньшей задачи — есть ли данные в наборе или нет.

Вот простой код Java, который делает это:

public static void getAllSubsets(int[] elements, int sum) {
    getAllSubsets(elements, 0, sum, new Stack<Integer>());
}
private static void getAllSubsets(int[] elements, int i, int sum, Stack<Integer> currentSol) { 
    //stop clauses:
    if (sum == 0 && i == elements.length) System.out.println(currentSol);
    //if elements must be positive, you can trim search here if sum became negative
    if (i == elements.length) return;
    //"guess" the current element in the list:
    currentSol.add(elements[i]);
    getAllSubsets(elements, i+1, sum-elements[i], currentSol);
    //"guess" the current element is not in the list:
    currentSol.pop();
    getAllSubsets(elements, i+1, sum, currentSol);
}

Обратите внимание, что если вы ищете все подмножества, их может быть экспоненциальное число, поэтому ожидается неэффективное решение с экспоненциальным временем.

Если вы хотите узнать, существует ли такой набор, или найти только один такой набор, это можно сделать намного эффективнее с помощью динамического программирования. В этом потоке объясняется логика того, как это можно сделать.
Обратите внимание, что задача по-прежнему NP-сложная, а "эффективное" решение на самом деле только псевдополиномиальное.

Я думаю, что основная проблема в вашем предыдущем подходе заключается в том, что простое выполнение циклов на основе входного массива не будет охватывать все комбинации чисел, соответствующие целевому значению. Например, если ваш основной цикл находится в ith, и после того, как вы выполните итерацию по элементу jth в своем вторичном цикле, ваша будущая комбинация, основанная на том, что вы собрали через i-й элемент, никогда больше не будет включать jth. Интуитивно говоря, этот алгоритм будет собирать все видимые комбинации через числа рядом друг с другом, но недалеко друг от друга.

Я написал итеративный подход, чтобы справиться с этой проблемой суммы подмножества через C++ (извините, у меня нет под рукой среды Java: P), идея в основном такая же, как и у рекурсивного подхода, что означает, что вы будете записывать все существующие комбинации чисел во время каждой итерации в вашем цикле. У меня есть один vector<vector> intermediate, используемый для записи всех встречающихся комбинаций, значение которых меньше целевого, и vector<vector> final, используемый для записи всех комбинаций, сумма которых равна целевому.

Подробное объяснение записано в строке:

/* sum the vector elements */
int sum_vec(vector<int> tmp){
    int sum = 0;
    for(int i = 0; i < tmp.size(); i++)
        sum += tmp[i];
    return sum;
}

static void naiveSubset(vector<int> arr, int target){
    /* sort the array from big to small, easier for us to
     * discard combinations bigger than target */
    sort(arr.begin(), arr.end(), greater<int>());

    int sum=0;
    vector<vector<int> > intermediate;
    vector<vector<int> > final;
    for (int i=0; i< arr.size();i++){
        int curr_intermediate_size = intermediate.size();
        for(int j = 0; j < curr_intermediate_size; j++){
            int tmpsum = sum_vec(intermediate[j]);
            /* For each selected array element, loop through all 
             * the combinations at hand which are smaller than target,
             * dup the combination, put it into either intermediate or 
             * final based on the sum */
            vector<int> new_comb(intermediate[j]);
            if(tmpsum + arr[i] <= target){
                new_comb.push_back(arr[i]);
                if(tmpsum + arr[i] == target)
                    final.push_back(new_comb);
                else
                    intermediate.push_back(new_comb);
            }
        }
        /* finally make the new selected element a separate entry
         * and based on its value, to insert it into either intermediate
         * or final */
        if(arr[i] <= target){
            vector<int> tmp;
            tmp.push_back(arr[i]);
            if(arr[i] == target)
                final.push_back(tmp);
            else
                intermediate.push_back(tmp);
        }
    }
    /* we could print the final here */
}

Только что написал это, поэтому, пожалуйста, потерпите меня, если есть какой-то угловой случай, который я не учел. Надеюсь это поможет:)