038 Combination Sum II.py

"""
Given a collection of candidate numbers (C) and a target number (T),
find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, ..., ak) must be in non-descending order. (i.e., a1 <= a2 <= ... <= ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
Author: Rajeev Ranjan
"""

class Solution:
    def combinationSum2(self, candidates, target):
        """
        dfs
        :param candidates: a list of integers
        :param target: integer
        :return: a list of lists of integers
        """
        result = []
        candidates.sort()
        self.get_combination_sum(candidates, [], target, result)
        return result

    def get_combination_sum(self, candidates, cur, target, result):
        """
        dfs with post-order jump
        :param candidates: a list of integers
        :param cur: a list of integers
        :param target: integer
        :param result: a list of lists of integers
        :return:
        """
        if sum(cur)==target:
            result.append(cur)
            return
        if sum(cur)>target:
            return

        # for ind, element in enumerate(candidates):
        #    self.get_combination_sum(candidates[ind+1:], cur+[element], target, result)

        # consider [1, 1, 1, 6], target 8
        ind = 0
        while ind<len(candidates):
            self.get_combination_sum(candidates[ind+1:], cur+[candidates[ind]], target, result)
            # post-order jump
            while ind+1<len(candidates) and candidates[ind]==candidates[ind+1]: ind+= 1  # jump to avoid duplicate
            ind += 1

if __name__=="__main__":
    print Solution().combinationSum2([10, 1, 2, 7, 6, 1, 5], 8)