Combination Sum 1 Editorial

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

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 may be used multiple times 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 which gave the target sum, and recurse for other choices.

Analysis

• Time Complexity: Exponential
• Space Complexity: Exponential

Implementation

C++

void findAllCombinations (vector<int>& A, int target, int index, vector<vector<int>> &result, vector<int> &current) {
	if (target == 0) {
		result.push_back(current);
		return;
	}
	if (index == A.size() || target < 0 ) {
		return;
	}
	current.push_back(A[index]);
	findAllCombinations (A, target - A[index], index, result, current);
	current.pop_back();
	findAllCombinations(A, target, index+1, result, current);      
}	
vector<vector<int> > combinationSum(vector<int> &A, int val) {
	vector<vector<int>> result;
	vector<int> current;
	findAllCombinations(A, val, 0, result, current);
	return result;
}

Java

class Solution {
	void findAllCombinations (int[] A, int target, int index, List<List<Integer>> result, List<Integer> current) {
		if (target == 0) {
			result.add(new ArrayList<>(current));
			return;
		}
		if (index == A.length || target < 0 ) {
			return;
		}
		current.add(A[index]);
		findAllCombinations (A, target - A[index], index, result, current);
		current.remove(current.size()-1);
		findAllCombinations(A, target, index+1, result, current);      
	}
	
	List<List<Integer>> combinationSum(int[] A, int val) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		List<Integer> current = new ArrayList<Integer>();
		findAllCombinations(A, val, 0, result, current);
		return result;
	}
}