LeetCode Combination Sum I,II,III,IV

introduce

Small goal of leetcode 300
This is a kind of problem, which can be solved by backtrack. Here, we will compare the similarities and differences. First, Combination Sum I, problem: given an int array, which does not contain repeated numbers, now you need to take some numbers from it repeatedly to make their sum target, and return all different fetches. There are two aspects to consider here: 1. Each time you add data to the arr, for example, add 1, the rest is to find and all the possibilities for target-1 in the data set, and save the data. If the final target is less than 0, then it will be returned and added to the list if it is equal to or equal to 0; 2. The same data will be added every time, and the rest of the starting point will start from the added data, for example, 1, to the most Final result = target, then add to the list. In order to prevent duplicate results from being saved, each time we traverse from the current position of the array. (see variable start in code I).

Then Combination Sum II. Unlike the first question, an array contains repeated numbers, but cannot be retrieved repeatedly. The method is still backtracking, but the starting position of each backtracking needs to be changed to start+1. Another difference is that there are duplicate data. In order to prevent duplicate records, we first sort the array from small to large, and use HashSet to remove duplicate results. See code 2 below.

Finally, Combination Sum III. Now we need to choose kkk different numbers from 1 to 9 to make their sum nnn. In this way, the length of each possible result is limited, that is, kkk. Not afraid, we add another variable to the backtracking to record the length of the current result, or directly use the length of the current result arr to compare with the target kkk. The general idea of backtracking is the same, but the judgment and boundary conditions of each backtracking change. See code 3 below.

In a word, we can't do without change. If we want to ask for f(target), we will try to add an element a first, and then the rest of the results will become f(target-a), and so on, until the final value is 0, so that we can even meet the combination of conditions once.

There is also a Combination Sum IV, but this can be solved with DP. See the following 4 for the code.

Java code

Combination Sum I code:

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList();
        dfs(list, new ArrayList<Integer>(), candidates,target,0,0);
        return list;
    }
    public void dfs(List<List<Integer>> list, List<Integer> arr, int[] candidates, int target, int sum, int start){
        if(sum >target) return;
        if(sum==target){
            list.add( new ArrayList<>(arr));
            return;
        }
        else{
            for(int i=start;i<candidates.length;i++){
                arr.add(candidates[i]);
                dfs(list,arr,candidates,target,sum+candidates[i],i);
                arr.remove(arr.size()-1);
            }
        }
    }

Combination Sum II:

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList();
        Arrays.sort(candidates);
        dfs(list, new ArrayList<Integer>(), candidates,target,0,0);
        HashSet hs = new HashSet(list);
        list.clear();
        list.addAll(hs);
        return list;
    }
    public void dfs(List<List<Integer>> list, List<Integer> arr, int[] candidates, int target, int sum, int start){
        if(sum >target) return;
        if(sum==target){
            list.add( new ArrayList<>(arr));
            return;
        }
        else{
            for(int i=start;i<candidates.length;i++){
                arr.add(candidates[i]);
                dfs(list,arr,candidates,target,sum+candidates[i],i+1);
                arr.remove(arr.size()-1);
            }
        }
    }

Combination Sum III:

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList();
        dfs(list, new ArrayList<Integer>(), n, 1, k);
        return list;
    }
    public void dfs(List<List<Integer>> list, List<Integer> arr, int tar, int start, int num){
        if(tar<0||arr.size()>num) return;
        if(tar==0&&arr.size()==num){
            list.add(new ArrayList<>(arr));
            return;
        }
        else{
            for(int i=start;i<=tar&&i<=9;i++){
                arr.add(i);
                dfs(list,arr,tar-i,i+1,num);
                arr.remove(arr.size() - 1);
            }
        }
    }

Combination Sum IV:

    public int combinationSum4(int[] nums, int target) {
        int dp[] = new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int j=0;j<nums.length;j++){
                if(i>=nums[j]) dp[i] += dp[i-nums[j]];
            }
        }
        return dp[target];
    }
42 original articles published, 10 praised, 20000 visitors+
Private letter follow

Tags: REST less Java

Posted on Fri, 13 Mar 2020 20:25:00 -0700 by avario