[Leetcode 216][Medium]组合总和 III--回溯(组合问题)

目录

一、题目描述

二、整体思路

三、代码

---

一、题目描述

原题地址

二、整体思路

        对于组合问题，首先要想到回溯法。那么可以根据回溯法模版进行设计。

void backtrace(元素){if(满足题目要求的条件){保存目前路径/状态/结果;return;}for循环,往目前状态相邻的所有可能的状态进行遍历{往下一个状态去的所需要进行的操作;backtrace(下一个状态);//递归调用backtrace;回溯操作,还原成目前状态。}}

        理解回溯法的本质是穷举所有可能的状态,通过递归来使得可以在原状态的基础上进入下一个状态，也就是入栈。那么不停地入栈直到没有可进入的状态时,递归函数进行出栈。

        那么函数出栈时,我们需要把当前状态还原成原状态，因为之前进入的下一个状态随着出栈已经结束了。 

三、代码

        

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> temp=new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtrace(1,k,n);return res;}void backtrace(int l,int k,int n){//l表示遍历到的数,n表示距离相差之和还有多远if(temp.size()==k){if(n==0){res.add(new ArrayList<>(temp));//不要直接用temp,因为temp是引用,如果直接用temp回溯时会改变temp,res里面的元素也会改变}return;}for(int i=l;i<=9;i++){//所有可能的状态就是1-9temp.add(i);backtrace(i+1,k,n-i);temp.remove(temp.size()-1);}return;}
}