Count distinct permutations of an array that sums to a target
Given an array of distinct positive integers, find the total number of distinct permutations that add up to a given target, where each array element may be used any number of times.
For example,
Output: 4
Explanation: The permutations of [1, 2, 3, 4] with sum 3 are:
[1, 1, 1]
[1, 2]
[2, 1]
[3]
Input: nums = [1, 3, 5], target = 5
Output: 5
Explanation: The permutations of [1, 3, 5] with sum 5 are:
[1, 1, 1, 1, 1]
[1, 1, 3]
[1, 3, 1]
[3, 1, 1]
[5]
We can use recursion to solve this problem. The idea is to consider each element in the array, and recur to see if the target can be reached by choosing the current number. If choosing a number results in the solution, we increment the total number of permutations found so far. Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <vector> using namespace std; int findPermutations(vector<int> const &nums, int target) { // if target is reached, return 1 if (target == 0) { return 1; } // if target cannot be reached, return 0 if (target < 0) { return 0; } // initialize the result with 0 int count = 0; // do for each number for (int i : nums) { // recur to see if target can be reached by including the current number `i` count += findPermutations(nums, target - i); } // return the total number of permutations return count; } int main() { vector<int> nums = {1, 2, 3, 4}; int target = 3; cout << findPermutations(nums, target) << endl; return 0; } |
Output:
4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class Main { public static int findPermutations(int[] nums, int target) { // if target is reached, return 1 if (target == 0) { return 1; } // if target cannot be reached, return 0 if (target < 0) { return 0; } // initialize the result with 0 int count = 0; // do for each number for (int i : nums) { // recur to see if target can be reached by including the current number `i` count += findPermutations(nums, target - i); } // return the total number of permutations return count; } public static void main(String[] args) { int[] nums = {1, 2, 3, 4}; int target = 3; System.out.println(findPermutations(nums, target)); } } |
Output:
4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def findPermutations(nums, target): # if target is reached, return 1 if target == 0: return 1 # if target cannot be reached, return 0 if target < 0: return 0 # initialize the result with 0 count = 0 # do for each number for i in nums: # recur to see if target can be reached by including the current number `i` count += findPermutations(nums, target - i) # return the total number of permutations return count if __name__ == '__main__': nums = [1, 2, 3, 4] target = 3 print(findPermutations(nums, target)) |
Output:
4
Since each recursive call is making n recursive calls, the time complexity of the above solution is exponential and it requires extra space for the call stack.
When the recursion tree is drawn for higher values of the target, we can see that the problem can be divided into smaller subproblems that are repeated. In other words, we will ultimately end up computing the same subproblem several times. Dynamic programming can be used to solve problems with optimal substructure and overlapping subproblems, where the subproblem solutions are memoized rather than repeatedly computed.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <vector> #include <climits> using namespace std; int findPermutations(vector<int> const &nums, int target, vector<int> &T) { // if target is reached, return 1 if (target == 0) { return 1; } // if target cannot be reached, return 0 if (target < 0) { return 0; } // if the subproblem is solved before, return the saved result if (T[target] != INT_MIN) { return T[target]; } // check if target can be reached by including each number int count = 0; for (int i : nums) { count += findPermutations(nums, target - i, T); } // save and return solution to the current subproblem T[target] = count; return count; } int findPermutations(vector<int> const &nums, int target) { // create an array to store the subproblems solution vector<int> T(target + 1, INT_MIN); return findPermutations(nums, target, T); } int main() { vector<int> const &nums = {1, 2, 3, 4}; int target = 3; cout << findPermutations(nums, target) << endl; return 0; } |
Output:
4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
import java.util.Arrays; class Main { public static int findPermutations(int[] nums, int target, int[] T) { // if target is reached, return 1 if (target == 0) { return 1; } // if target cannot be reached, return 0 if (target < 0) { return 0; } // if the subproblem is solved before, return the saved result if (T[target] != Integer.MIN_VALUE) { return T[target]; } // check if target can be reached by including each number int count = 0; for (int i : nums) { count += findPermutations(nums, target - i, T); } // save and return solution to the current subproblem T[target] = count; return count; } public static int findPermutations(int[] nums, int target) { int[] T = new int[target + 1]; Arrays.fill(T, Integer.MIN_VALUE); return findPermutations(nums, target, T); } public static void main(String[] args) { int[] nums = {1, 2, 3, 4}; int target = 3; System.out.println(findPermutations(nums, target)); } } |
Output:
4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
import sys def findPermutations(nums, target, T=None): # create a list to store the subproblems solution if not T: T = [-sys.maxsize] * (target + 1) # if target is reached, return 1 if target == 0: return 1 # if target cannot be reached, return 0 if target < 0: return 0 # if the subproblem is solved before, return the saved result if T[target] != -sys.maxsize: return T[target] # check if target can be reached by including each number count = 0 for i in nums: count += findPermutations(nums, target - i, T) # save and return solution to the current subproblem T[target] = count return count if __name__ == '__main__': nums = [1, 2, 3, 4] target = 3 print(findPermutations(nums, target)) |
Output:
4
The time complexity of the above memoized solution is O(n.target), where n is the size of the array. The auxiliary space used by the program is O(target).
Even better, we can write a bottom-up variant of the above memoized version. By starting with smaller subproblems and working our way up, we can solve larger subproblems. The bottom-up method calculates T[i] using the smaller values of i that have already been computed.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <vector> using namespace std; int findPermutations(vector<int> const &nums, int target) { // create an array to store the solution of the subproblems vector<int> T(target + 1); // there is only one way to reach the target of 0 - don't consider any element T[0] = 1; // fill T[] in bottom-up manner for (int t = 1; t < T.size(); t++) { for (int i : nums) { if (t - i >= 0) { T[t] += T[t - i]; } } } // last element of T[] stores the result return T[target]; } int main() { vector<int> nums = {1, 2, 3}; int target = 4; cout << findPermutations(nums, target) << endl; return 0; } |
Output:
4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Main { public static int findPermutations(int[] nums, int target) { // create an array to store the solution of the subproblems int[] T = new int[target + 1]; // there is only one way to reach the target of 0 - don't consider any element T[0] = 1; // fill T[] in bottom-up manner for (int i = 1; i < T.length; i++) { for (int k : nums) { if (i - k >= 0) { T[i] += T[i - k]; } } } // last element of T[] stores the result return T[target]; } public static void main(String[] args) { int[] nums = {1, 2, 3}; int target = 4; System.out.println(findPermutations(nums, target)); } } |
Output:
4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
def findPermutations(nums, target): # create an array to store the solution of the subproblems T = [0] * (target + 1) # there is only one way to reach the target of 0 - don't consider any element T[0] = 1 # fill T[] in bottom-up manner for i in range(1, len(T)): for k in nums: if i - k >= 0: T[i] += T[i - k] # last element of T[] stores the result return T[target] if __name__ == '__main__': nums = [1, 2, 3] target = 4 print(findPermutations(nums, target)) |
Output:
4
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)