Combination Sum

Last Updated : 28 Jan, 2025

Given an array of distinct integers arr[] and an integer target, the task is to find a list of all unique combinations of array where the sum of chosen element is equal to target.

Note: The same number may be chosen from array an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Examples:

Input: arr[] = [2, 4, 6, 8], target = 8
Output: [[2, 2, 2, 2],
[2, 2, 4],
[2, 6],
[4, 4],
[8]]

Input: arr[] = [2, 7, 6, 5], target = 16
Output: [[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 6],
[2, 2, 2, 5, 5],
[2, 2, 5, 7],
[2, 2, 6, 6],
[2, 7, 7],
[5, 5, 6]]

Approach: Using backtracking

The idea is to use backtracking and recursively explore all possible combinations of elements, of the given array that sums up to given target value. If the remaining sum becomes less than 0 then backtrack to explore other possible combinations.

Step by step implementation

To perform recursion, create an array cur[] to store the current combination and a 2D array res[] to store all valid combinations. Start from the 0^thelement and for each element arr[i], there are two choices:
- Include the element: Add it to array cur and reduce remSum by arr[i] and move to the same index as we can choose same element multiple times.
- Skip the element: Move to the next element without adding the current.
If the remaining sum becomes 0, add the current combination cur to res else backtrack to previous element by removing the element from the last index of cur.

C++

// C++ program to find all combinations that
// sum to a given target
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to generate all combinations
// of arr that sums to target.
void makeCombination(vector<int> &arr, int remSum, vector<int> &cur, 
                     vector<vector<int>> &res, int index) {
    
    // If remSum is 0 then add the combination to the result
    if (remSum == 0) {
        res.push_back(cur);
        return;
    }

    // Invalid Case: If remSum is less than 0 or if ind >= arr.size()
    if (remSum < 0 || index >= arr.size())
        return;
	
    // add the current element to the combination
    cur.push_back(arr[index]);

    // recur with the same index
    makeCombination(arr, remSum - arr[index], cur, res, index);

    // remove the current element from the combination
    cur.pop_back();
  
	// recur with the next index
    makeCombination(arr, remSum, cur, res, index + 1);
}

// Function to find all combinations of elements
// in array arr that sum to target.
vector<vector<int>> combinationSum(vector<int> &arr, int target) {
  	sort(arr.begin(), arr.end());

    // vector to store combinations
    vector<int> cur;

    // vector to valid combinations
    vector<vector<int>> res;
    makeCombination(arr, target, cur, res, 0);

    return res;
}

int main() {
    vector<int> arr = {2, 4, 6, 8};
    int target = 8;

    vector<vector<int>> res = combinationSum(arr, target);

    for (vector<int> &v : res) {
        for (int i : v) {
            cout << i << " ";
        }
        cout << endl;
    }

    return 0;
}

Java

// Java program to find all combinations that
// sum to a given target
import java.util.ArrayList;
import java.util.Arrays;

class GfG {

    // Function to generate all combinations
    // of arr that sums to target.
    static void makeCombination(int[] arr, int remSum, ArrayList<Integer> cur, 
                                       ArrayList<ArrayList<Integer>> res, int index) {
        
        // If remSum is 0 then add the combination to the result
        if (remSum == 0) {
            res.add(new ArrayList<>(cur));
            return;
        }

        // Invalid Case: If remSum is less than 0 or if index >= arr.length
        if (remSum < 0 || index >= arr.length)
            return;
        
        // Add the current element to the combination
        cur.add(arr[index]);

        // Recur with the same index
        makeCombination(arr, remSum - arr[index], cur, res, index);

        // Remove the current element from the combination
        cur.remove(cur.size() - 1);

        // Recur with the next index
        makeCombination(arr, remSum, cur, res, index + 1);
    }

    // Function to find all combinations of elements
    // in array arr that sum to target.
    static ArrayList<ArrayList<Integer>> combinationSum(int[] arr, int target) {
      	Arrays.sort(arr);

        // List to store combinations
        ArrayList<Integer> cur = new ArrayList<>();

        // List to store valid combinations
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        makeCombination(arr, target, cur, res, 0);

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8};
        int target = 8;

        ArrayList<ArrayList<Integer>> res = combinationSum(arr, target);

        for (ArrayList<Integer> v : res) {
            for (int i : v) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}

Python

# Python program to find all combinations that
# sum to a given target

# Function to generate all combinations
# of arr that sums to target.
def makeCombination(arr, remSum, cur, res, index):

    # If remSum is 0 then add the combination to the result
    if remSum == 0:
        res.append(list(cur))
        return

    # Invalid Case: If remSum is less than 0 or if index >= len(arr)
    if remSum < 0 or index >= len(arr):
        return

    # Add the current element to the combination
    cur.append(arr[index])

    # Recur with the same index
    makeCombination(arr, remSum - arr[index], cur, res, index)

    # Remove the current element from the combination
    cur.pop()

    # Recur with the next index
    makeCombination(arr, remSum, cur, res, index + 1)

# Function to find all combinations of elements
# in array arr that sum to target.
def combinationSum(arr, target):
    arr.sort()

    # List to store combinations
    cur = []

    # List to store valid combinations
    res = []
    makeCombination(arr, target, cur, res, 0)
    
    return res

if __name__ == "__main__":
    arr = [2, 4, 6, 8]
    target = 8

    res = combinationSum(arr, target)

    for v in res:
        print(" ".join(map(str, v)))

// C# program to find all combinations that
// sum to a given target
using System;
using System.Collections.Generic;

class GfG {

    // Function to generate all combinations
    // of arr that sums to target.
    static void makeCombination(int[] arr, int remSum, List<int> cur, 
                                 List<List<int>> res, int index) {
        
        // If remSum is 0 then add the combination to the result
        if (remSum == 0) {
            res.Add(new List<int>(cur));
            return;
        }

        // Invalid Case: If remSum is less than 0 or if index >= arr.Length
        if (remSum < 0 || index >= arr.Length)
            return;

        // Add the current element to the combination
        cur.Add(arr[index]);

        // Recur with the same index
        makeCombination(arr, remSum - arr[index], cur, res, index);

        // Remove the current element from the combination
        cur.RemoveAt(cur.Count - 1);

        // Recur with the next index
        makeCombination(arr, remSum, cur, res, index + 1);
    }

    // Function to find all combinations of elements
    // in array arr that sum to target.
    static List<List<int>> combinationSum(int[] arr, int target) {
      	Array.Sort(arr);

        // List to store combinations
        List<int> cur = new List<int>();

        // List to store valid combinations
        List<List<int>> res = new List<List<int>>();
        makeCombination(arr, target, cur, res, 0);

        return res;
    }

    static void Main(string[] args) {
        int[] arr = {2, 4, 6, 8};
        int target = 8;

        List<List<int>> res = combinationSum(arr, target);

        foreach (var v in res) {
            foreach (int i in v) {
                Console.Write(i + " ");
            }
            Console.WriteLine();
        }
    }
}

JavaScript

// JavaScript program to find all combinations that
// sum to a given target

// Function to generate all combinations
// of arr that sums to target.
function makeCombination(arr, remSum, cur, res, index) {
    
    // If remSum is 0 then add the combination to the result
    if (remSum === 0) {
        res.push([...cur]);
        return;
    }

    // Invalid Case: If remSum is less than 0 or if index >= arr.length
    if (remSum < 0 || index >= arr.length)
        return;

    // Add the current element to the combination
    cur.push(arr[index]);

    // Recur with the same index
    makeCombination(arr, remSum - arr[index], cur, res, index);

    // Remove the current element from the combination
    cur.pop();

    // Recur with the next index
    makeCombination(arr, remSum, cur, res, index + 1);
}

// Function to find all combinations of elements
// in array arr that sum to target.
function combinationSum(arr, target) {
	arr.sort((a, b) => a - b);

    // Array to store combinations
    const cur = [];

    // Array to store valid combinations
    const res = [];
    makeCombination(arr, target, cur, res, 0);

    return res;
}

// Driver Code
const arr = [2, 4, 6, 8];
const target = 8;
const res = combinationSum(arr, target);

for (const v of res) {
    console.log(v.join(" "));
}

Output

Time Complexity: O(K * 2^k), where K is average size of a valid combination and k = Target / min(arr), depth of the recursion tree.
Auxiliary Space: O(k), considering the recursive stack and neglecting the space required to store the combinations.

Warnsdorff's algorithm for Knight’s tour problem

GeeksforGeeks

Improve

Article Tags :

Practice Tags :

Combination Sum

Approach: Using backtracking

Similar Reads

Standard problems on backtracking

Easy Problems on Backtracking

Medium prblems on Backtracking

Hard problems on Backtracking

Thank You!

What kind of Experience do you want to share?