Combination Sum I

題目要求：給定一個數(shù)組（元素?zé)o重復(fù)），和一個目標(biāo)值，找到所有組合，加起來等于目標(biāo)值。數(shù)組中的元素可以重復(fù)使用.

因?yàn)槲覀兛梢越M合任意多個數(shù)，然后確認(rèn)其和是否為目標(biāo)數(shù)，并且返回所有可能的組合，所以必須遍歷所有可能性才能求解。

如果遍歷所有的可能，這必然會導(dǎo)致效率的問題，所以避免重復(fù)搜索，我們搜索的時候只搜索當(dāng)前或之后的數(shù)，不搜索之前的元素。

這是非常典型的DFS并且返回路徑的題目，我們采用DFS的方法，在搜索之前我們首先進(jìn)行排序，因?yàn)閿?shù)組有可能是亂序的。

public class combinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result=new LinkedList<>();//返回的列表
        List<Integer> temp=new LinkedList<>();//臨時列表
        //首先進(jìn)行排序，避免重復(fù)搜索
        Arrays.sort(candidates);//排序
        combin(candidates,target,0,temp,result);
        //返回列表
        return result;
    }
    private void combin(int[] arrays,int target,int index,List<Integer> temp,List<List<Integer>> result){
        //如果目標(biāo)和的差值小于0，表示該路徑出現(xiàn)錯誤
        if (target<0){
            return;
        //等于表示，這是一條正確的路徑，將其add到result上
        }else if (target==0){
           //這里每次重新創(chuàng)建temp列表，避免與之前的列表重復(fù)
            result.add(new LinkedList<>(temp));
        //否則的話，目標(biāo)和的差值大于0，繼續(xù)進(jìn)行深度優(yōu)先搜索
        }else {
            //選取之后的每個數(shù)字都是一種可能性，其中index的作用是避免搜索之前搜索過的數(shù)組元素
            for (int i=index;i<arrays.length;i++){
                temp.add(arrays[i]);
                //先加入元素，然后進(jìn)行搜索，這里進(jìn)行DFS搜索，如果不滿足，就把temp列表里的元素去除掉
                combin(arrays,target-arrays[i],i,temp,lists);
               //目標(biāo)和不符合，所以將臨時列表的最新值去除，然后嘗試下一個元素
                temp.remove(temp.size()-1);
            }
        }
    }
}

Combination Sum II

題目要求：給定一個數(shù)組（元素可以有重復(fù)），和一個目標(biāo)值，找到所有組合，加起來等于目標(biāo)值。數(shù)組中的元素不能重復(fù)使用。

這個題目與1的區(qū)別就是同一個數(shù)只能選取一次，而且結(jié)果也不能重復(fù)。所以我們進(jìn)行遞歸的時候在下標(biāo)加1，這樣下一次搜索的時候就避免了重復(fù)搜索自己的情況。

并且要防止重復(fù)搜索相同的元素，所以要本輪搜索跳過相同的元素。這里我們依然采用DFS的方法，并且先進(jìn)行排序，理由同上。

public class combinationSum2 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result=new LinkedList<>();
        List<Integer> temp=new LinkedList<>();
        Arrays.sort(candidates);
        combin(candidates,target,0,temp,result);
        return lists;
    }
    private void combin(int[] array,int target,int index,List<Integer> temp,List<List<Integer>> result){
        if (target<0){
            return;
        }else if (target==0){
            list.add(new LinkedList<>(temp));
        }else {
            for (int i=index;i<array.length;i++){
                // 跳過本輪剩余的重復(fù)元素
                if(i>index &&array[i]==array[i-1]) continue;
                temp.add(array[i]);
                // 遞歸時下標(biāo)加1
                combin(array,target-array[i],i+1,temp,result);
                temp.remove(temp.size()-1);
            }
        }
    }
}

Combination Sum III

題目要求：給定K和N，從1--9中這幾個9個數(shù)字組合出來K個數(shù)，其和為N。1-9不能重復(fù)使用.

這一題是上一題的簡化版，與之不同的是這里沒有數(shù)組，并且要返回在1~9之內(nèi)滿足目標(biāo)和的列表個數(shù)，同一個元素只能選擇一次。所以進(jìn)行搜索的時候可以跳過重復(fù)元素的部分，由于要求列表的長度要等于k，所以我們還要對于k進(jìn)行控制。

這里依然采用DFS的方法。

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result=new LinkedList<>();  //返回的列表
        List<Integer>temp=new LinkedList<>();//臨時列表
        combin(k,n,1,temp,result);
        return result;
    }
    private void combin(int k,int target,int index,List<Integer> temp,List<List<Integer>> result){
        //這里對于k進(jìn)行控制，若是列表長度大于k仍然沒有符合要求，直接返回
        if(target<0||temp.size()>k){
            return;
        //這里加上一個控制條件
        }else if(target==0&&temp.size()==k){
            result.add(new LinkedList<>(temp));
            return;
        }else{
           //這里不使用數(shù)組元素，只用使用1~9即可
            for(int i=index;i<=9;i++){
                temp.add(i);
                //這里i+1是指跳過自己
                combin(k,target-i,i+1,temp,result);
                temp.remove(temp.size()-1);
            }
        }
    }
}

Combination Sum IV

題目要求：給定一個正整數(shù)數(shù)組（元素?zé)o重復(fù)），給定目標(biāo)target，找出組合的個數(shù)，使得組合中元素的和等于target。數(shù)組元素可以重復(fù)使用.

一開始嘗試使用DFS的思路來解題，沒想到時間超時，于是發(fā)現(xiàn)這一題是動態(tài)規(guī)劃的題目。

我們首先建立一個一維數(shù)組dp，長度為target+1，dp[i]存儲的是目標(biāo)i時所得到的組合數(shù)。

從dp[1]開始計(jì)算到dp[target]，每次計(jì)算dp[i]時的方法是，從頭開始遍歷nums數(shù)組。

如果i>=nums[j],dp[i]=dp[i]+dp[i-nums[j]]

（比如題目中的例子[1，2，3]
計(jì)算dp[1] ：
從頭開始遍歷nums
當(dāng)j =0時 因?yàn)? >= nums[0] 故 dp[1] = dp[1]+dp[1- nums[0]],即
dp[1] = dp[1]+dp[0] = 1;
當(dāng)j=1 時 因?yàn)? < nums[1] 故 不再運(yùn)算 故dp[1] = 1;
計(jì)算 dp[2]:
當(dāng)j =0時 因?yàn)? >= nums[0] 故 dp[2] = dp[2]+dp[2- nums[0]],即
dp[2] = dp[2]+dp[1] = 1;
當(dāng)j =1時 因?yàn)? >= nums[1] 故 dp[2] = dp[2]+dp[2- nums[1]],即
dp[2] = dp[2]+dp[0] = 2;
當(dāng)j=2 時 因?yàn)? < nums[2] 故 不再運(yùn)算 故dp[2] = 2;

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int[] dp=new int[target+1];
        for(int i=1;i<dp.length;i++){
            for(int num:nums){
                if (num == i) dp[i]++;
                else if (num < i) dp[i] += dp[i-num];
                else break;
            }
        }
        return dp[target];
    }
}

這一題參考了下面的連接。

參考：https://segmentfault.com/a/1190000008607396

上述代碼已放在我的GitHub中：https://github.com/heiqi1/LeetCode