Leetcode --- Combination Sum I
===

## Description

Given an array of **distinct** integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

**The same number may be chosen from candidates an unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

=> 在給定的input array中,找出所有可能的組合加總等於target

### Examples

* Ex1:

**Input**: candidates = [2,3,6,7], target = 7
**Output**: [[2,2,3],[7]]
**Explanation**:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

* Ex2:

**Input**: candidates = [2,3,5], target = 8
**Output**: [[2,2,2,2],[2,3,3],[3,5]]

* Ex3:

**Input**: candidates = [2], target = 1
**Output**: []

* Ex4:

**Input**: candidates = [1], target = 1
**Output**: [[1]]

* Ex5:

**Input**: candidates = [1], target = 2
**Output**: [[1,1]]

### Constraints:

* 1 <= candidates.length <= 30
* 1 <= candidates[i] <= 200
* All elements of candidates are distinct.
* 1 <= target <= 500

## Solution:

尚未想出使用linear algebra的解法,因為Ax=b,A是給的input array,b是target,然而就算解出X~c~= X~p~+ X~n~後,因為輸入只有一列,所以rank必等於1<=>dim(N(A))=n-1,這樣狀況下的通解仍要考慮是否為整數才能是本題的解,所有會有n-1個任意數需要慢慢帶入,複雜度會到指數.

另一解使用DFS的觀念下去解,對每個input element往下探索,其中要注意自己也要是探索對象.

Ex: 2,3,6,7 target =7


class Solution {
  
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
       
        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)
        {
            ans.add(new ArrayList<>(tmp));
            return;
        }
        else
        {
            for(int i =start;i<candidates.length;i++)
            {
                sum += candidates[i];
                tmp.add(candidates[i]);
                
                DFS(i,target,sum,candidates,ans,tmp);
                sum -= candidates[i];
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

副程式中分三種case:
* sum(總和) > target :必須捨掉最後一個加進來的數,並往下探索加別人
* sum = target :找到一組組合,存入答案中,但存入答案後仍要捨去掉最後一個加進來的數,並往下探索加別人
* sum < target :sum往上加總剛加進來的數,並建立數組,為找到答案後做準備.

**line 17:** 若使用**ans.add(tmp);** 而不是**ans.add(new ArrayList<>(tmp));** 會產生的問題:因為list.add(e)是將插入物件的==位址==append進list內,所以只要當tmp被更改而整個ans也會被更改,所以將當下儲存解的tmp,插入新create的Arraylist就不會一起被替換掉了.下面給個簡單的例子即能明白.

import java.util.*;
public class Main
{
	public static void main(String[] args) {
	     List<List<Integer>> ans = new ArrayList<>();
	     List<Integer> tmp = new ArrayList<>();
        D(ans,tmp);
		
	}
	public static void D(List<List<Integer>> ans,List<Integer> tmp)
    {
        tmp.add(5);
        ans.add(tmp);
        System.out.println("before :"+ans);
        tmp.add(6);
        System.out.println("after :"+ans);
        return;
    }
}
//Output:
// before : [[5]]
// after  : [[5,6]]

**line 22~30:** 遞迴加迴圈運作流程.以下給個簡單範例:

#include <stdio.h>
int main()
{
    DFS(0,0);
    return 0;
}
void DFS(int st,int k)
{
    k++ ;
    if(k==3 )
        return;
    else
    {
        for(int i =st ; i<2 ; i++)
        {
            printf("i = %d, k = %d\n",i,k);
            DFS(i,k);
        }
    }
}
//Output
// i=0 , k=1
// i=0 , k=2
// i=1 , k=2
// i=1 , k=1
// i=1 , k=2


### Submissions on Leetcode

Runtime: **8 ms**, faster than **13.92%** of Java online submissions for Combination Sum.
Memory Usage: **41.3 MB**, less than **6.57%** of Java online submissions for Combination Sum.

### Complexity Analysis

It is O(N^target) because we are looping through all the targets and the max number of candidates to get to target will be 'target'
Ex: cand[1,2,3], target=7
Max number of candidates to get to 7 is 1+1+1+1+1+1+1 (target number of 1)
We do not know if we have a 1 on the candidates, but we need to consider the worst case.

因為可以重複挑選且有可能出現1在input array,當發生時會是worse case:必須重複挑target個而複雜度為
=> ==O(2^target^)==

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