欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-22 20:16:15
【算法-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[] cand...

【算法-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