【算法-Java实现】组合总和

一.问题描述：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

比如：

输入：[2,3,6,7]；输出：[[7], [2, 2, 3]]

输入：[3,4,5,6,7,8,9]；输出：[[8], [4, 4], [3, 5]]

本题来源：力扣39

二.问题解答：

思路：搜索回溯

递归函数结构体：

dfs(int[] candidates,int target,List<List> ans,List combine,int index)

candidates：输入的数组；
target：目标值；
ans：返回的结果；
combine：返回结果的子结果（可行解）；
index：数组下标（从0开始进行递归）

使用递归，两种情况：

1.dfs( candidates, target, ans,combine,index+1)：每一次递归都对index加1，接着进行递归；

递归终止条件：index==candidates.length；

2.对元素大小进行判断，若candidates[index]<target,表示candidates[index]可以构成可行解;

进行递归：dfs(candidates, target-candidates[index], ans, combine, index)，改变target的值，index不变（因为每个元素可以出现多次）。

三.算法分析：

1.时间复杂度为O(S)，S为所有可行解的长度之和

2.额外空间复杂度为O(target)，本题使用递归，递归本质是调用计算机栈帮我们执行，空间复杂度取决于递归的栈深度，在最差的情况下需要递归O(target)层。

代码如下

/*
 * 问题：组合总和
 * 方法：搜索回溯(递归)
 */
import java.sql.Array;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Solution {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		String str=in.nextLine();
		int target=in.nextInt();
		String[] strAyyay=str.split(",");
		int[] candidates=new int[strAyyay.length];
		for(int i=0;i<candidates.length;i++) {
			candidates[i]=Integer.parseInt(strAyyay[i]);
		}
		List<List<Integer>> ans=combinationSum( candidates, target);
		System.out.println(ans);
	}
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
    	List<List<Integer>> ans=new ArrayList<List<Integer>>();
    	List<Integer> combine=new ArrayList<>();
    	//index=0，从第一个元素开始递归
    	dfs(candidates,target,ans,combine,0);
    	return ans;
    }
    public static void dfs(int[] candidates,int target,List<List<Integer>> ans,List<Integer> combine,int index) {
    	//index从0开始累加，当index等于数组长度时，表示已经对前index-1个元素(即全部元素)完成递归
    	if(index==candidates.length) {
    		return;
    	}
    	//每一次递归，当传入的target==0，即表示已经找到可行解，将combine添加至ans中
    	if(target==0) {
    		ans.add(new ArrayList<Integer>(combine));
    		return;
    	}
    	//index每次加1进行递归
    	dfs( candidates, target, ans,combine,index+1);
    	//对元素进行判断,若元素小于target,添加元素至combine中
    	if(target-candidates[index]>=0) {
    		combine.add(candidates[index]);
    		//改变target值，再次递归，因为每个元素可以被使用多次，所以index不变
    		dfs(candidates, target-candidates[index], ans, combine, index);
    		//combine要存储每一次的可能结果，所以每次都要进行移除操作，让combine为空，方便下一次操作
    		combine.remove(combine.size()-1);
    	}
    }
}

本文地址：https://blog.csdn.net/hkdhkdhkd/article/details/109273264