377.Combination Sum IV

Tags: [DP]

Link: https://leetcode.com/problems/combination-sum-iv/#/description

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]

target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

Credits:
Special thanks to@pbrotherfor adding this problem and creating all test cases.

Solution: DP

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums or not target:
            return 0

        # DP formula:
        # f[t] = sum(f[t - nums[i]]), t >= nums[i]
        f = [0 for _ in xrange(target + 1)]
        f[0] = 1

        for t in xrange(1, target + 1):
            for elem in nums:
                if t >= elem:
                    f[t] += f[t - elem]

        return f[target]

Revelation:

• Because the target is the sum of the elements, that means target = sub_target + one_element, we can think if we just only need one more element then we can get to target, and this one more element can be any element in the given nums, which means num_of_combination(target) = sum(num_of_combination(target - one_element)), and this one_element can be nums[i]. So the DP formula is: f[t] = sum(f[t - nums[i]]), t >= nums[i]. For example, the given nums = [1, 2, 3], and target = 4, so f[4] = sum(f[4 - nums[i]]), so f[4] = f[3] + f[2] + f[1]. And the f[0] should be 1, because there is only one combination to make the target is 0, and this combination is empty array.
• Question: Why this DP formula is also calculating the number of permutations (the element order does matter)???

Note:

• Time complexity = O(target * n), target is the given target, and n is the number of given elements.

Follow-Up:

• If there exists the negative numbers, for example, nums = [1, -1], and target = 10, then we can build an infinite sequence to achieve the goal, such [1, -1, 1, -1, 1, -1......]. So if there exits negative numbers, we should add the 'max length of sequence' as the limitation to this question. then it seems we can use the 'recursion' approach to solve the problem, add 'limit_len' in the recursion function's arguments, and maybe we can pass a memo to the recursion, to achieve the DP

Time Limited Exceeded

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target == 0:
            return 1

        rest = 0
        for elem in nums:
            if target >= elem:
                rest += self.combinationSum4(nums, target - elem)

        return rest

Revelation:

• Base on the above idea, this is the recursion solution.

Time Limited Exceeded

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums or not target:
            return 0

        combination_set = set()
        buff = []
        combinations = []
        self.get_combinations(nums, 0, target, buff, combinations, combination_set)

        counter = 0
        for combination in combinations:
            counter += self.get_num_of_permutations(combination)

        return counter

    def get_combinations(self, nums, index, target, buff, combinations, combination_set):
        # base case
        s = sum(buff)
        if s > target:
            return
        if s == target:
            combination_str = str(buff)
            if combination_str not in combination_set:
                combination_set.add(combination_str)
                combinations.append(list(buff))
            return

        for i in xrange(index, len(nums)):
            buff.append(nums[i])

            self.get_combinations(nums, i, target, buff, combinations, combination_set)
            self.get_combinations(nums, i + 1, target, buff, combinations, combination_set)

            buff.pop()

    def get_num_of_permutations(self, arr):
        if not arr:
            return 0

        permutation_set = set()
        index_set = set()
        buff = []
        permutations = []
        self.get_permutations(arr, buff, permutations, index_set, permutation_set)

        return len(permutations)

    def get_permutations(self, arr, buff, permutations, index_set, permutation_set):
        # base case
        if len(buff) == len(arr):
            permutation_str = str(buff)
            if permutation_str not in permutation_set:
                permutation_set.add(permutation_str)
                permutations.append(list(buff))
            return

        for i in xrange(len(arr)):
            if i in index_set:
                continue

            index_set.add(i)
            buff.append(arr[i])

            self.get_permutations(arr, buff, permutations, index_set, permutation_set)

            buff.pop()
            index_set.remove(i)

Revelation:

• Get the combinations which can achieve the target, then get the permutations based on each combination.
• Use hash set to remove the duplicates of the combinations and permutations.

Note:

• Time complexity = O(n! * n!), n is the number of given elements.