The Royal Coding
Addition And Subtraction Of Two Matrices Alphabet Traingle Array Rotation Binary To Octal Calculate Power Using Recurssion Current Date And Time Floyds Traingle Largest Element Of A Given Array Lower To Upper And Upper To Lower Cases Multiplication Of Two Matrix Number Of Duplicate Characters In A String Octal Number To Decimal Pascals Triangle Print A Pyramid Using Star Program To Convert Binary To Decimal Number Reverse A Sentence Using Recursion Reverse An Array Or List Separate Even Or Odd Standard Deviation Sum Of All Elements In Array Transpose Of Two Matrices Combination Sum

Python/C/C++/JAVA

Moderate Practice Programs with Code and Concept

By D.S

Combination Sum

The Combination Sum problem requires finding all unique combinations of numbers from an array that sum up to a target value. Each number can be used multiple times.
Example:
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[7], [2, 2, 3]]
Explanation:

  • [7] uses 7 directly.
  • [2, 2, 3] sums to 7 by using 2 twice and 3 once.
    • This problem is solved using backtracking:
  • Recursively explore combinations.
  • At each step, either include or skip a number.
  • Backtrack when a combination exceeds the target.

    • (a.) C Code

    #include <stdio.h>
          #include <stdlib.h>
          
          void backtrack(int* candidates, int candidatesSize, int target, int start, int* temp, int tempSize, int** result, int* returnSize, int* columnSizes) {
              if (target == 0) {
                  result[*returnSize] = malloc(tempSize * sizeof(int));
                  for (int i = 0; i < tempSize; i++) {
                      result[*returnSize][i] = temp[i];
                  }
                  columnSizes[*returnSize] = tempSize;
                  (*returnSize)++;
                  return;
              }
              
              if (target < 0) return;
              
              for (int i = start; i < candidatesSize; i++) {
                  temp[tempSize] = candidates[i];
                  backtrack(candidates, candidatesSize, target - candidates[i], i, temp, tempSize + 1, result, returnSize, columnSizes);
              }
          }
          
          int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** columnSizes) {
              *returnSize = 0;
              int** result = malloc(1000 * sizeof(int*));
              *columnSizes = malloc(1000 * sizeof(int));
              int* temp = malloc(1000 * sizeof(int));
              
              backtrack(candidates, candidatesSize, target, 0, temp, 0, result, returnSize, *columnSizes);
              
              free(temp);
              return result;
          }
          
          // Example Usage
          int main() {
              int candidates[] = {2, 3, 6, 7};
              int target = 7;
              int returnSize;
              int* columnSizes;
              
              int** result = combinationSum(candidates, 4, target, &returnSize, &columnSizes);
              
              for (int i = 0; i < returnSize; i++) {
                  printf("[");
                  for (int j = 0; j < columnSizes[i]; j++) {
                      printf("%d", result[i][j]);
                      if (j < columnSizes[i] - 1) printf(", ");
                  }
                  printf("]\n");
                  free(result[i]);
              }
              free(result);
              free(columnSizes);
              return 0;
          }
    Output:-
    [2, 2, 3]
    [7]

    (b.) C++ Code

    #include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& candidates, int target, vector<int>& temp, vector<vector<int>>& result, int start) {
    if (target == 0) {
        result.push_back(temp);
        return;
    }
    if (target < 0) return;
    
    for (int i = start; i < candidates.size(); i++) {
        temp.push_back(candidates[i]);
        backtrack(candidates, target - candidates[i], temp, result, i);
        temp.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> temp;
    backtrack(candidates, target, temp, result, 0);
    return result;
}

// Example Usage
int main() {
    vector<int> candidates = {2, 3, 6, 7};
    int target = 7;
    
    vector<vector<int>> result = combinationSum(candidates, target);
    
    for (auto& combination : result) {
        cout << "[";
        for (int i = 0; i < combination.size(); i++) {
            cout << combination[i];
            if (i < combination.size() - 1) cout << ", ";
        }
        cout << "]\n";
    }
    return 0;
}
    Output:-
    [2, 2, 3]
    [7]

    (c.) Python Code

    def combinationSum(candidates, target):
        def backtrack(start, target, path, result):
            if target == 0:
                result.append(path[:])
                return
            if target < 0:
                return
            
            for i in range(start, len(candidates)):
                path.append(candidates[i])
                backtrack(i, target - candidates[i], path, result)
                path.pop()
        
        result = []
        backtrack(0, target, [], result)
        return result
    
    # Example Usage
candidates = [2, 3, 6, 7]
target = 7
print(combinationSum(candidates, target))
    Output:-
    [2, 2, 3]
    [7]

    (d.) Java Code

    import java.util.ArrayList;
import java.util.List;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> temp, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        if (target < 0) return;

        for (int i = start; i < candidates.length; i++) {
            temp.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, temp, result);
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();
        int[] candidates = {2, 3, 6, 7};
        int target = 7;

        List<List<Integer>> result = cs.combinationSum(candidates, target);
        for (List<Integer> combination : result) {
            System.out.println(combination);
        }
    }
}
    Output:-
    [2, 2, 3]
    [7]

    How did you feel about this post?

    😍 🙂 😐 😕 😡

    Was this helpful?

    👍 👎