力扣hot100 组合总和 回溯 剪枝 组合

• 算法结构

Problem: 39. 组合总和

在这里插入图片描述

文章目录

  • 思路
  • 复杂度
  • 💖 Code

思路

复杂度

时间复杂度:

O

(

n

)

O(n)

O(n)

空间复杂度:

O

(

n

)

O(n)

O(n)

💖 Code

class Solution{
	List<List> res = new ArrayList();
	int x;// 全局target
	int[] c;// 全局 candidates

	public List<List> combinationSum(int[] candidates, int target)
	{
		if (candidates == null || candidates.length == 0)
			return new ArrayList();
		x = target;
		c = candidates;
		dfs(0, 0, new ArrayList());
		return res;
	}

	/**
	 * @param sum  当前已选数的和
	 * @param idx  当前选到的数的下标，下标 < idx 的数都不能选，防止重复
	 * @param list 当前已选数列表
	 */
	private void dfs(int sum, int idx, ArrayList list)
	{
		if (sum >= x)// >= x 就返回
		{
			if (sum == x)// 只有 == x 时，才加入答案集合
				res.add(new ArrayList(list));
			return;
		}
		//从idx开始，idx前面的数选几个已经定了
		for (int i = idx; i < c.length; i++)
		{
			list.add(c[i]);
			dfs(sum + c[i], i, list);
			list.remove(list.size() - 1);
		}
	}
}

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/8f54d1df51.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐