Leetcode --- Combination Sum II
===

## Description

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

**Each number in candidates may only be used once in the combination.**

Note: The solution set must **not contain duplicate** combinations.

Input Array中的element可能會有重複,但每個element只能被用一次,而相同數列不同排列順序必須剃除在答案之外.

### Examples

* Ex1:
**Input:** candidates = [10,1,2,7,6,1,5], target = 8
**Output**
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
* Ex2:
**Input:** candidates = [2,5,2,1,2], target = 5
**Output:**
[
[1,2,2],
[5]
]

### Constarints

* 1 <= candidates.length <= 100
* 1 <= candidates[i] <= 50
* 1 <= target <= 30

## Solution

與Combination Sum I解題思路相同,透過DFS的想法,不過這次不允許自己被再次使用且重複的答案必須拿掉.

### Method 1:重複的使用function:array.indexOf()去檢查

class Solution {
    public static int foo =0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(candidates);
        
        DFS(0,target,0,candidates,ans,tmp);
        
        return ans;
    }
    private void DFS(int start,int target,int sum,int[] candidates,List<List<Integer>> ans,List<Integer> tmp)
    {
        if(sum > target)
            return;
        else if(sum == target)
        {
            if(ans.indexOf(tmp) == -1)
                ans.add(new ArrayList<Integer>(tmp));
            return;
        }
        else
        {
            for(int i =start;i<candidates.length;i++)
            {
                sum +=candidates[i];
                tmp.add(candidates[i]);
                try
                {
                    DFS(++start,target,sum,candidates,ans,tmp);
                } 
                catch(Exception e)
                {
                    DFS(start,target,sum,candidates,ans,tmp);
                }
                sum-= candidates[i];
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

Line 6:必須先sort後面才能找到相同的數列去剃除
Line 28:使用try防止超出存取陣列範圍的Exception
Line 30:不存取自己所已++start

#### Submissions on Leetcode

Runtime: **929 ms, faster than 5.00%** of Java online submissions for Combination Sum II.
Memory Usage: **40 MB, less than 13.48%** of Java online submissions for Combination Sum II.

#### Complexity Analysis

Worse case:O(2^n^)

### Method 2:
優化速度,重複的就不進遞迴了且採用Backtracking,
為什麼倒著找會比順著找還快呢?我猜是因為我們的Array排列成ascending order,下面給出descending order的範例

* Ascending order且backtracking:

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(candidates);
        
        DFS(0,target,candidates,ans,tmp);
        
        return ans;
    }
    private void DFS(int start,int target,int[] candidates,List<List<Integer>> ans,List<Integer> tmp)
    {
        if(target <0)
            return;
        else if(target == 0)
        {
            ans.add(new ArrayList<>(tmp));
            return;
        }
        else
        {
            for(int i= start;i<candidates.length;i++)
            {
                if(i > start && candidates[i] == candidates[i-1])
                    continue;
                
                tmp.add(candidates[i]);
                DFS(i+1,target -candidates[i],candidates,ans,tmp);
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

Line 24:已我為中心往下探且下一個等於我則跳過

#### Submission on Leetcode

Runtime: **4 ms, faster than 65.98%** of Java online submissions for Combination Sum II.
Memory Usage: **39.2 MB, less than 53.77%** of Java online submissions for Combination Sum II.

**非常吃test data==,吐的好速度快,吐不好就很慢(3~10ms)**

* Descending order且順著找:

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(candidates);
        for(int i =0 ;i<candidates.length/2;i++)
        {
           candidates[i] ^= candidates[candidates.length-i-1];
            
           candidates[candidates.length-i-1] ^= candidates[i];
            
           candidates[i] ^= candidates[candidates.length-i-1];
        }
        
        DFS(0,target,0,candidates,ans,tmp);
        
        return ans;
    }
    private void DFS(int start,int target,int sum,int[] candidates,List<List<Integer>> ans,List<Integer> tmp)
    {
        if(sum> target )
            return;
        else if(target == sum)
        {
            ans.add(new ArrayList<>(tmp));
            return;
        }
        else
        {
            for(int i= start;i<candidates.length;i++)
            {
                if(i > start && candidates[i] == candidates[i-1])
                    continue;
               
                tmp.add(candidates[i]);
                DFS(i+1,target,sum+candidates[i],candidates,ans,tmp);
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

Line 5~13:先升序排列後再轉成降序排列

#### Submission on Leetcode
Runtime:**2 ms, faster than 99.02%** of Java online submissions for Combination Sum II.
Memory Usage: **38.9 MB, less than 91.94%** of Java online submissions for Combination Sum II.

**非常吃test data==,吐的好速度快,吐不好就很慢(3~10ms)**

#### Complexity Analysis

Worse case:O(2^n^)

###### tags: `Leetcode` `Medium` `DFS`