穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞

用户11305962

发布于 2025-01-13 08:34:43

4900

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

题目：

解析：

决策树：

代码设计：

代码：

写法一：path为全局变量

private int ret,path,aim;
    public int findTargetSumWays(int[] nums, int target) {
        aim = target;
        dfs(nums,0);
        return ret;
    }
    
    private void dfs(int[] nums, int pos){
        if(pos == nums.length){
            if(path == aim) ret++;
            return;
        } 

        //添加 '+'
        path += nums[pos];
        dfs(nums,pos+1);
        path -= nums[pos];//回溯

        //添加 '-'
        path -= nums[pos];
        dfs(nums,pos+1); 
        path += nums[pos];//回溯
    }

写法二：path作为参数

private int ret,aim;
    public int findTargetSumWays(int[] nums, int target) {
        aim = target;
        dfs(nums,0,0);
        return ret;
    }
    
    private void dfs(int[] nums, int pos,int path){
        if(pos == nums.length){
            if(path == aim) ret++;
            return;
        }

        //添加 '+'
        dfs(nums, pos+1, path + nums[pos]);

        //添加 '-'
        dfs(nums, pos+1, path - nums[pos]); 
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs