leetcode 216. Combination Sum III | 216. 组合总和 III（Java）

小灰灰 2022-10-07 04:56 143阅读 0赞

## 题目 ##

[https://leetcode.com/problems/combination-sum-iii/][https_leetcode.com_problems_combination-sum-iii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

回溯法（back tracking）是一种选优搜索法。可以理解为通过选择不同的岔路口寻找目的地，一个岔路口一个岔路口的去尝试找到目的地。如果走错了路，继续返回来找到岔路口的另一条路，直到找到目的地。

对于本题来说，维护一个 `boolean[] arr` 数组，用来记录每个元素是否被选累加。process 的过程是，从左至右遍历，对于每一个位置来说，都有加与不加两种选择。分别对这两种选择调用 process，以此类推。直到越界，或累加和恰好为目标值时，返回。

import java.util.ArrayList;
    import java.util.List;
    
    class Solution { 
        int target = 0;
        List<List<Integer>> resultList;
    
        public List<List<Integer>> combinationSum3(int k, int n) { 
            target = n;
            resultList = new ArrayList<>();
            process(new boolean[10], 1, 0, k);
            return resultList;
        }
    
        public void process(boolean[] arr, int i, int sum, int valid) { 
            if (i >= 10 || sum > target || valid <= 0) return; // 越界
            if (sum + i == target && valid - 1 == 0) {  // 成功匹配之后 由于后面的数字只可能更大 所以后面不再可能匹配 直接返回即可
                arr[i] = true;
                ArrayList<Integer> list = new ArrayList<>();
                for (int j = 1; j < 10; j++) { 
                    if (arr[j]) list.add(j);
                }
                resultList.add(list);
            }
            process(arr, i + 1, sum, valid);
            arr[i] = true; // 修改之后要恢复原值 以保持原状返还给上一个函数继续使用
            process(arr, i + 1, sum + i, valid - 1);
            arr[i] = false;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_combination-sum-iii]: https://leetcode.com/problems/combination-sum-iii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/f4e51d6f268d423bb99ba5f116f24627.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/eaffa3ca68b740c49f244831bc495137.png