подмножество sum найти все подмножества, которые составляют число

Question

Я изучаю динамическое программирование, и я хочу немного поменять классическую проблему с подмножеством, распечатав все подмножества, которые составляют число. Как именно я буду заниматься этим? В настоящее время, я знаю, как печатать истинным или ложным в зависимости от того существует подмножество, которое добавляет к нему

public static boolean hasSum(int [] array, int sum) 
{ 
    int len = array.length; 
    boolean[][] table = new boolean[sum+1][len+1]; 

    int i; 

    for(i = 0; i <= len; i++) 
     table[0][i] = true; 

    for(i = 1; i <= sum; i++) 
     table[i][0] = false; 

    for(i = 1; i <= sum; i++) 
    { 
     for(int j = 1; j <= len; j++) 
     { 
      table[i][j] = table[i][j-1]; 

      if(!table[i][j] && i >= array[j-1]) 
       table[i][j] = table[i-array[j-1]][j-1]; 
     } 
    }   

    return table[sum][len]; 
} 

, если это возможно, я хотел бы вернуть массив всех подмножеств.

Answer 1

Эта проблема сложнее, чем оригинальная.

Для каждого table[i][j], который вы установили в true, вы должны пометить все свои предшественников т.е. всех table[i1][j1]=true, благодаря которому вы отметили table[i][j] как истинные. Таким образом вы создаете своего рода структуру графика. Вершинами этого графа являются пары (i,j).

Затем, когда вы хотите напечатать ответ, вам нужно отследить от (i,j) ко всему возможному (i1,j1) и т. Д. Назад. Для этого просто массива будет недостаточно, вам понадобятся дополнительные/вспомогательные структуры данных.