Рубрики

Задача идеальной суммы (вывести все подмножества с заданной суммой)

Заданный массив целых чисел и сумма, задача состоит в том, чтобы напечатать все подмножества данного массива с суммой, равной данной сумме.

Примеры:

Input : arr[] = {2, 3, 5, 6, 8, 10}
        sum = 10
Output : 5 2 3
         2 8
         10

Input : arr[] = {1, 2, 3, 4, 5}
        sum = 10
Output : 4 3 2 1 
         5 3 2 
         5 4 1 

Спросил в Tesco

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

Как и в предыдущем посте , мы строим 2D-массив dp [] [] таким образом, чтобы dp [i] [j] сохранял значение true, если сумма j возможна с элементами массива от 0 до i.
После заполнения dp [] [] мы рекурсивно обходим его из dp [n-1] [sum]. Для прохождения ячейки мы сохраняем путь до достижения его и рассматриваем две возможности для элемента.
1) Элемент включен в текущий путь.
2) Элемент не включен в текущий путь.

Всякий раз, когда сумма становится 0, мы прекращаем рекурсивные вызовы и печатаем текущий путь.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для подсчета всех подмножеств с
// заданная сумма.
#include <bits/stdc++.h>

using namespace std;

  
// dp [i] [j] будет хранить true, если сумма j
// возможно с элементами массива от 0 до i.

bool** dp;

  

void display(const vector<int>& v)

{

    for (int i = 0; i < v.size(); ++i)

        printf("%d ", v[i]);

    printf("\n");

}

  
// Рекурсивная функция для печати всех подмножеств с
// помощь dp [] []. Вектор p [] хранит текущее подмножество.

void printSubsetsRec(int arr[], int i, int sum, vector<int>& p)

{

    // Если мы достигли конца и сумма не равна нулю. Мы печатаем

    // p [] только если arr [0] равно sun ИЛИ dp [0] [sum]

    // правда.

    if (i == 0 && sum != 0 && dp[0][sum])

    {

        p.push_back(arr[i]);

        display(p);

        return;

    }

  

    // Если сумма становится 0

    if (i == 0 && sum == 0)

    {

        display(p);

        return;

    }

  

    // Если заданная сумма может быть достигнута после игнорирования

    // текущий элемент.

    if (dp[i-1][sum])

    {

        // Создать новый вектор для хранения пути

        vector<int> b = p;

        printSubsetsRec(arr, i-1, sum, b);

    }

  

    // Если данная сумма может быть достигнута после рассмотрения

    // текущий элемент.

    if (sum >= arr[i] && dp[i-1][sum-arr[i]])

    {

        p.push_back(arr[i]);

        printSubsetsRec(arr, i-1, sum-arr[i], p);

    }

}

  
// Печатает все подмножества arr [0..n-1] с суммой 0.

void printAllSubsets(int arr[], int n, int sum)

{

    if (n == 0 || sum < 0)

       return;

  

    // Сумма 0 всегда может быть достигнута с 0 элементами

    dp = new bool*[n];

    for (int i=0; i<n; ++i)

    {

        dp[i] = new bool[sum + 1];

        dp[i][0] = true;

    }

  

    // Сумма arr [0] может быть достигнута с одним элементом

    if (arr[0] <= sum)

       dp[0][arr[0]] = true;

  

    // Заполняем остальные записи в dp [] []

    for (int i = 1; i < n; ++i)

        for (int j = 0; j < sum + 1; ++j)

            dp[i][j] = (arr[i] <= j) ? dp[i-1][j] ||

                                       dp[i-1][j-arr[i]]

                                     : dp[i - 1][j];

    if (dp[n-1][sum] == false)

    {

        printf("There are no subsets with sum %d\n", sum);

        return;

    }

  

    // Теперь рекурсивно обходим dp [] [], чтобы найти все

    // пути из dp [n-1] [sum]

    vector<int> p;

    printSubsetsRec(arr, n-1, sum, p);

}

  
// Код драйвера

int main()

{

    int arr[] = {1, 2, 3, 4, 5};

    int n = sizeof(arr)/sizeof(arr[0]);

    int sum = 10;

    printAllSubsets(arr, n, sum);

    return 0;

}

Джава

// Java-программа для подсчета всех подмножеств с заданной суммой.

import java.util.ArrayList;

public class SubSet_sum_problem

{

    // dp [i] [j] будет хранить true, если сумма j

    // возможно с элементами массива от 0 до i.

    static boolean[][] dp;

       

    static void display(ArrayList<Integer> v)

    {

       System.out.println(v);

    }

       

    // Рекурсивная функция для печати всех подмножеств с

    // помощь dp [] []. Вектор p [] хранит текущее подмножество.

    static void printSubsetsRec(int arr[], int i, int sum, 

                                         ArrayList<Integer> p)

    {

        // Если мы достигли конца и сумма не равна нулю. Мы печатаем

        // p [] только если arr [0] равно sun ИЛИ dp [0] [sum]

        // правда.

        if (i == 0 && sum != 0 && dp[0][sum])

        {

            p.add(arr[i]);

            display(p);

            p.clear();

            return;

        }

       

        // Если сумма становится 0

        if (i == 0 && sum == 0)

        {

            display(p);

            p.clear();

            return;

        }

       

        // Если заданная сумма может быть достигнута после игнорирования

        // текущий элемент.

        if (dp[i-1][sum])

        {

            // Создать новый вектор для хранения пути

            ArrayList<Integer> b = new ArrayList<>();

            b.addAll(p);

            printSubsetsRec(arr, i-1, sum, b);

        }

       

        // Если данная сумма может быть достигнута после рассмотрения

        // текущий элемент.

        if (sum >= arr[i] && dp[i-1][sum-arr[i]])

        {

            p.add(arr[i]);

            printSubsetsRec(arr, i-1, sum-arr[i], p);

        }

    }

       

    // Печатает все подмножества arr [0..n-1] с суммой 0.

    static void printAllSubsets(int arr[], int n, int sum)

    {

        if (n == 0 || sum < 0)

           return;

       

        // Сумма 0 всегда может быть достигнута с 0 элементами

        dp = new boolean[n][sum + 1];

        for (int i=0; i<n; ++i)

        {

            dp[i][0] = true;  

        }

       

        // Сумма arr [0] может быть достигнута с одним элементом

        if (arr[0] <= sum)

           dp[0][arr[0]] = true;

       

        // Заполняем остальные записи в dp [] []

        for (int i = 1; i < n; ++i)

            for (int j = 0; j < sum + 1; ++j)

                dp[i][j] = (arr[i] <= j) ? (dp[i-1][j] ||

                                           dp[i-1][j-arr[i]])

                                         : dp[i - 1][j];

        if (dp[n-1][sum] == false)

        {

            System.out.println("There are no subsets with"

                                                  " sum "+ sum);

            return;

        }

       

        // Теперь рекурсивно обходим dp [] [], чтобы найти все

        // пути из dp [n-1] [sum]

        ArrayList<Integer> p = new ArrayList<>();

        printSubsetsRec(arr, n-1, sum, p);

    }

      

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        int arr[] = {1, 2, 3, 4, 5};

        int n = arr.length;

        int sum = 10;

        printAllSubsets(arr, n, sum);

    }

}
// Этот код предоставлен Sumit Ghosh


Выход :

4 3 2 1 
5 3 2 
5 4 1 

Эта статья предоставлена Jas Kaur . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Задача идеальной суммы (вывести все подмножества с заданной суммой)

0.00 (0%) 0 votes