Combination Sum 2 Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/combination-sum-2

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array of distinct integers A and a target value val, find all unique combinations of integers from A where their sum is equal to val.

Note: Each integer in the array may be used once in the combination.

Approach

The approach to this problem is to use brute force recursion to backtrack through all possible choices of taking the array elements in our list. At every recursive call, we try to fit one of the current array element and see whether it is valid to add that current element to attain the given sum. Whenever we attain the given target, we return the current list of elements that gave the target sum and recurse for other choices.

Note: Since here each integer can be used once, we will sort the given array and while selecting an array element for the recursive call we will make sure that it is not equal to the previous element in the array.

Analysis

• Time Complexity: Exponential
• Auxiliary Space Complexity: O(1)

Implementation

C++

void findAllCombinations(vector<int> &A, int val, int start, int sum, vector<int> &currentCombination, vector<vector<int>> &allCombinations) {
	if(sum == val) {
		allCombinations.push_back(currentCombination);
		return;
	}
	for (int i = start; i < A.size(); i++) {
		if(A[i] + sum > val) {
			continue;
		}
		if(i > start && A[i] == A[i - 1]) {
			continue;
		}
		currentCombination.push_back(A[i]);
		findAllCombinations(A, val, i + 1, sum + A[i], currentCombination, allCombinations);
		currentCombination.pop_back();
	}
}
vector<vector<int> >combinationSum(vector<int> &A, int val) {
	vector<vector<int>> allCombinations;
    vector<int> currentCombination;
	sort(A.begin(), A.end());
	findAllCombinations(A, val, 0, 0, currentCombination, allCombinations);
	return allCombinations;
}

Java

class Solution {
	void findAllCombinations(int[] A, int val, int start, int sum, List<Integer> currentCombination, List<List<Integer>> allCombinations) {
		if(sum == val) {
			allCombinations.add(new ArrayList<> (currentCombination));
			return;
		}
		for (int i = start; i < A.length; i++) {
			if(A[i] + sum > val) {
				continue;
			}
			if(i > start && A[i] == A[i - 1]) {
				continue;
			}
			currentCombination.add(A[i]);
			findAllCombinations(A, val, i + 1, sum + A[i], currentCombination, allCombinations);
			currentCombination.remove(currentCombination.size() - 1);
		}
	}
	List<List<Integer>> combinationSum(int[] A, int val) {
	    List<List<Integer>> allCombinations = new ArrayList<List<Integer>> ();
		List<Integer> currentCombination = new ArrayList<Integer> ();
		Arrays.sort(A);
		findAllCombinations(A, val, 0, 0, currentCombination, allCombinations);
		return allCombinations;
	}
}