java-回溯算法学习中

回溯算法和递归密不可分，我们可以理解简单的递归，但是当我们刚接触回溯算法的时候，确实还是会比较晕。

可以通过一道题来观察回溯算法

Leet_216 组合3

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

    只使用数字1到9
    每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

来源：力扣（LeetCode）
 

//先创建两个集合准备存放结果和需要的过程
    List> list = new ArrayList<>();
    linkedList path = new linkedList<>();
    //测试
    @Test
    public void test1(){
        List> daan=combinationSum3(3,7);
        System.out.println(daan);
        //[[1, 2, 4]]
    }

    //方法调用
    public List> combinationSum3(int k, int n) {
        backTracking(n,k,1,0);

        return list;
    }
    //回溯方法
    
    public void backTracking(int Nsum,int k,int startIndex,int sum){
        if(sum>Nsum){
            return;
        }
        if(path.size()==k){
            if(sum==Nsum) list.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<=9;i++){//不剪枝也可以 i <= 9 - (k - path.size()) + 1
            path.add(i);
            sum+=i;
            backTracking(Nsum,k,i+1,sum);
            //回溯操作
            sum-=i;
            path.removeLast();
        }

    }