Java implements LeetCode (combined sum)

leetcode topic

Sum of Combinations--leetcode 39

Title description

Given 1 array candidates without repeating elements and 1 target number target,

Find out all the combinations in candidates that can make the number sum target.

Numbers in candidates can be selected indefinitely and repeatedly.

Description:

All numbers (including target) are positive integers.

Solution sets cannot contain duplicate combinations.  

Example 1:

Input: candidates = [2, 3, 6, 7], target = 7,

The set to be solved is:

[

  [7],

  [2,2,3]

]

Example 2:

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

The set to be solved is:

[

  [2,2,2,2],

  [2,3,3],

  [3,5]

]

Source: Force Buckle (LeetCode)

Link: https://leetcode-cn.com/problems/combination-sum

Copyright belongs to the collar button network. Please contact the official authorization for commercial reprinting, and please indicate the source for non-commercial reprinting.

Train of thought

Backtracking algorithm

Recursive summing is the combination of target, and the exit is sum exceeding target

Code

package com.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *  Title:  
 *  Combination sum  -- leetcode 39
 * 
 *  Title description: 
 * 
 Given 1 Array without repeating elements  candidates  And 1 Number of targets  target  , 
 Find out  candidates  All the numbers in which you can make the sum of numbers to  target  The combination of. 
candidates  Numbers in can be selected indefinitely and repeatedly. 

 Description: 
 All figures (including  target ) are positive integers. 
 Solution sets cannot contain duplicate combinations.  

 Example  1:
 Input : candidates = [2,3,6,7], target = 7,
 The set to be solved is :
[
  [7],
  [2,2,3]
]

 Example  2:
 Input : candidates = [2,3,5], target = 8,
 The set to be solved is :
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

 Source: Likou ( LeetCode ) 
 Links: https://leetcode-cn.com/problems/combination-sum
 Copyright belongs to the collar button network. Please contact the official authorization for commercial reprinting, and please indicate the source for non-commercial reprinting. 
 */
public class CombinationSum {
	/**
	 *  Thoughts:  
	 * 1 Backtracking algorithm 
	 * 2 , recursively find the sum for target The combination of exports is and exceeds target
	 */
    public List<List<Integer>> combinationSum(int[] bb, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (bb == null) {
            return res;
        }
        
        addCombinations(bb, 0, target, new ArrayList<Integer>(), res);
        
        return res;
    }
    
    private void addCombinations(int[] bb, int start, int target, List<Integer> cache, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(cache));
            return;
        }
        for (int i=start; i<bb.length; i++) {
            cache.add(bb[i]);
            addCombinations(bb,i,target-bb[i],cache,res);
            cache.remove(cache.size()-1);
        }
    }
	
    
    /**
     *  Thoughts:  
     *  Optimized backtracking 
     */
    public List<List<Integer>> combinationSumII(int[] bb, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (bb == null) {
            return res;
        }
        
        //  After sorting the array   You can reduce the number of recursions when recursive, and cooperate with  if (bb[i] > target) break;
        Arrays.sort(bb);
        
        addCombinationsII(bb, 0, target, new ArrayList<Integer>(), res);
        
        return res;
    }
    
    private void addCombinationsII(int[] bb, int start, int target, List<Integer> cache, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(cache));
            return;
        }
        for (int i=start; i<bb.length; i++) {
        	//  Match the sorted array   Improve performance 
            if (bb[i] > target) {
                break;
            }
            cache.add(bb[i]);
            addCombinationsII(bb,i,target-bb[i],cache,res);
            cache.remove(cache.size()-1);
        }
    }
}