Trouver une somme de valeurs égales à une valeur donnée - Programmation compétitive

Problème de la somme de sous-ensemble

Dans la leçon sur l'addition et la soustraction, un enseignant d'une école primaire utilise un ensemble de valeurs, puis donne aux élèves une valeur somme et leur demande s'ils peuvent former cette valeur à partir de l'ensemble donné.

Définition — Problème de la Somme de Sous-ensemble (Subset Sum) Étant donné un ensemble de n entiers positifs et une valeur somme, déterminer s'il existe un sous-ensemble de l'ensemble donné dont la somme des éléments est exactement égale à somme.

Ce problème est un classique de la programmation dynamique et appartient à la classe des problèmes NP-Complet.

Énoncé du problème

Entrée

La première ligne contient deux valeurs : somme et n.
La deuxième ligne contient n valeurs qui forment l'ensemble.

Sortie

Oui s'il existe un tel sous-ensemble, sinon Non.

Exemple 1

Entrée

15 5
7 2 8 6 9

Sortie

Oui

Explication : 6 + 9 = 15 ✓ — le sous-ensemble {6, 9} atteint la somme cible.

Exemple 2

Entrée

0 3
2 5 6

Sortie

Oui

Explication : Le sous-ensemble vide {} a une somme de 0. somme = 0 → toujours Oui.

Exemple 3

Entrée

15 4
1 2 7 3

Sortie

Non

Explication : La somme maximale possible est 1+2+7+3 = 13 < 15. Aucun sous-ensemble ne peut atteindre 15.

Contraintes

1 ≤ n ≤ 10³
0 ≤ somme ≤ 10⁴
Les valeurs de l'ensemble sont des entiers positifs

Solution naïve — Récursive

L'idée est d'explorer tous les sous-ensembles possibles de manière récursive. Pour chaque élément, on a exactement deux choix :

Inclure le dernier élément → somme requise devient somme - vals[n-1], nombre d'éléments devient n - 1
Ignorer le dernier élément → somme requise reste somme, nombre d'éléments devient n - 1

Arbre de récursion — Exemple : vals = {7, 2, 8, 6, 9}, somme = 15 Chaque nœud représente un appel solution(n, somme) :

solution(5, 15)
├── solution(4, 15)   [ignorer 9]
│   ├── solution(3, 15)   [ignorer 6]
│   └── solution(3, 9)    [inclure 6]  → 6+9=15 ✓
└── solution(4, 6)    [inclure 9]
    └── ...

Cas de base de la récursion C++/Python

si somme == 0  → retourner true   // sous-ensemble vide
si n == 0      → retourner false  // ensemble vide, somme non atteinte
si vals[n-1] > somme → ignorer cet élément (impossible de l'inclure)

#include <iostream>
#include <vector>
using namespace std;

bool solution(vector<int> vals, int n, int somme) {

    // Cas de base
    if (somme == 0) return true;
    if (n == 0)     return false;

    // Si le dernier élément est supérieur à somme, ignorez-le
    if (vals[n - 1] > somme)
        return solution(vals, n - 1, somme);

    // Deux choix : inclure ou ignorer le dernier élément
    return solution(vals, n - 1, somme)               // ignorer
        || solution(vals, n - 1, somme - vals[n - 1]); // inclure
}

int main() {
    int somme, n, val;
    cin >> somme >> n;
    vector<int> valeurs;
    for (int i = 0; i < n; i++) {
        cin >> val;
        valeurs.push_back(val);
    }
    solution(valeurs, n, somme) ? cout << "Oui" : cout << "Non";
    return 0;
}

import sys

def solution(vals, n, somme):

    # Cas de base
    if somme == 0: return True
    if n == 0:     return False

    # Si le dernier élément est supérieur à somme, ignorez-le
    if vals[n - 1] > somme:
        return solution(vals, n - 1, somme)

    # Deux choix : inclure ou ignorer le dernier élément
    return (solution(vals, n - 1, somme)                  # ignorer
         or solution(vals, n - 1, somme - vals[n - 1]))   # inclure


somme, n = map(int, sys.stdin.readline().strip().split())
valeurs  = list(map(int, sys.stdin.readline().strip().split()))

print("Oui" if solution(valeurs, n, somme) else "Non")

Sortie (Exemple 1)

Oui

Complexité — Solution récursive naïve Dans le pire des cas, la récursion explore tous les 2ⁿ sous-ensembles possibles.
Complexité temporelle : O(2ⁿ) — exponentielle.
Complexité spatiale : O(n) — profondeur de la pile d'appels.

Le problème est NP-Complet : il n'existe pas de solution polynomiale connue. Cependant, pour des valeurs de somme raisonnables, la programmation dynamique offre une solution pseudo-polynomiale efficace.

Solution — Programmation Dynamique (Bottom-Up)

Pour résoudre le problème en temps pseudo-polynomial, on utilise la programmation dynamique avec un tableau 2D.

Définition — Tableau DP On crée un tableau booléen DP[n+1][somme+1] où :

DP[i][j] = true s'il existe un sous-ensemble de vals[0..i-1] dont la somme vaut exactement j.

Règle de remplissage du tableau Pour chaque case DP[i][j]:

Si j < vals[i-1] : impossible d'inclure l'élément i → DP[i][j] = DP[i-1][j]
Si j ≥ vals[i-1] : on peut inclure ou ignorer → DP[i][j] = DP[i-1][j] OR DP[i-1][j - vals[i-1]]

Cas de base :

DP[i][0] = true pour tout i (somme 0 → sous-ensemble vide)
DP[0][j] = false pour j ≥ 1 (ensemble vide, somme non nulle impossible)

Illustration — vals = {7, 2, 8, 6, 9}, somme = 15

i \ j	0	1	2	6	7	8	9	14	15
0 ({})	✓	✗	✗	✗	✗	✗	✗	✗	✗
1 ({7})	✓	✗	✗	✗	✓	✗	✗	✗	✗
2 ({7,2})	✓	✗	✓	✗	✓	✗	✗	✗	✗
5 ({7,2,8,6,9})	✓	✗	✓	✓	✓	✓	✓	✓	✓

DP[5][15] = true → Oui

#include <iostream>
#include <vector>
using namespace std;

bool solution(vector<int> &vals, int n, int somme) {

    // Tableau DP de taille (n+1) x (somme+1)
    bool DP[n + 1][somme + 1];

    // Initialisation : somme = 0 → toujours vrai (sous-ensemble vide)
    for (int i = 0; i <= n; i++)
        DP[i][0] = true;

    // Initialisation : ensemble vide, somme > 0 → toujours faux
    for (int j = 1; j <= somme; j++)
        DP[0][j] = false;

    // Remplissage Bottom-Up
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= somme; j++) {
            if (j < vals[i - 1])
                // Impossible d'inclure vals[i-1], copier l'état précédent
                DP[i][j] = DP[i - 1][j];
            else
                // Inclure OU ignorer vals[i-1]
                DP[i][j] = DP[i - 1][j] || DP[i - 1][j - vals[i - 1]];
        }
    }

    return DP[n][somme];
}

int main() {
    int somme, n, val;
    cin >> somme >> n;
    vector<int> valeurs;
    for (int i = 0; i < n; i++) {
        cin >> val;
        valeurs.push_back(val);
    }
    solution(valeurs, n, somme) ? cout << "Oui" : cout << "Non";
    return 0;
}

import sys

def solution(vals, n, somme):

    # Tableau DP de taille (n+1) x (somme+1), initialisé à False
    DP = [[False] * (somme + 1) for _ in range(n + 1)]

    # somme = 0 → toujours vrai (sous-ensemble vide)
    for i in range(n + 1):
        DP[i][0] = True

    # ensemble vide, somme > 0 → toujours faux (déjà False par défaut)
    for j in range(1, somme + 1):
        DP[0][j] = False

    # Remplissage Bottom-Up
    for i in range(1, n + 1):
        for j in range(1, somme + 1):
            if j < vals[i - 1]:
                DP[i][j] = DP[i - 1][j]          # ignorer obligatoirement
            else:
                DP[i][j] = (DP[i - 1][j]          # ignorer
                          or DP[i - 1][j - vals[i - 1]])  # inclure

    return DP[n][somme]


somme, n = map(int, sys.stdin.readline().strip().split())
valeurs  = list(map(int, sys.stdin.readline().strip().split()))

print("Oui" if solution(valeurs, n, somme) else "Non")

Sortie (Exemple 1)

Oui

Complexité — Solution Programmation Dynamique

Critère	Solution récursive naïve	Programmation dynamique
Temps	O(2ⁿ) — exponentiel	O(n × somme) — pseudo-polynomial
Espace	O(n) — pile d'appels	O(n × somme) — tableau 2D
Sous-problèmes recalculés	Oui — nombreux recalculs	Non — mémoïsation implicite

Optimisation mémoire — Tableau 1D On peut réduire l'espace à O(somme)en utilisant un seul tableau 1D parcouru de droite à gauche (pour éviter d'utiliser un élément deux fois) :

vector<bool> dp(somme + 1, false);
dp[0] = true;
for (int val : vals)
    for (int j = somme; j >= val; j--)   // parcours à rebours !
        dp[j] = dp[j] || dp[j - val];
return dp[somme];

Cette variante est dite optimisation de l'espace du Subset Sum DP.

Points clés à retenir

Le problème de la somme de sous-ensemble consiste à déterminer s'il existe un sous-ensemble d'éléments dont la somme égale une valeur cible.
La solution récursive naïve a une complexité exponentielle O(2ⁿ).
La programmation dynamique permet de résoudre le problème en temps pseudo-polynomial O(somme × n).
L'approche dynamique utilise un tableau 2D booléen où DP[i][j] indique s'il est possible d'obtenir la somme j avec les i premiers éléments.
Ce problème est NP-Complet dans le cas général, mais la solution dynamique est efficace pour des valeurs de somme modérées.
Une optimisation mémoire permet de réduire l'espace à O(somme) avec un tableau 1D parcouru à rebours.

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

récursivité Tableaux

Trouver une somme de valeurs égales à une valeur donnée - Programmation compétitive

Problème de la somme de sous-ensemble

Énoncé du problème

Entrée

Sortie

Solution naïve — Récursive

Solution — Programmation Dynamique (Bottom-Up)

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Trouver une somme de valeurs égales à une valeur donnée - Programmation compétitive

Problème de la somme de sous-ensemble

Énoncé du problème

Entrée

Sortie

Solution naïve — Récursive

Solution — Programmation Dynamique (Bottom-Up)

Discussion (0)

Laisser un commentaire