回溯法

题目大意：

  给一个正整数列表alist和指定正整数T，不限定每个数的使用次数，返回任意元素相加之和等于指定数的所有组合的链表。形如：alist = [1,3,6,4,2,7] T = 8 ,返回链表[[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 3], [1, 1, 1, 4], [1, 1, 1, 2, 2], [1, 1, 3, 2], [1, 3, 3], [1, 6], [1, 4, 2], [1, 2, 2, 2], [3, 4], [3, 2, 2], [7]]。

思路：

  使用回溯法（不撞南墙不回头，一旦撞了墙，就该按照原路回头了）

代码实现：

package com.lm.main.searching;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class GettingList2 {
    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> cur = new LinkedList<>();

    private void DFS(int[] arr, int pos, int curSum, int sum) {
        if (pos == arr.length) {
            return;
        }

        cur.add(arr[pos]);

        if (curSum == sum) {
            result.add(new ArrayList<>(cur));
            return;
        }
        if (curSum > sum) {
            return;
        }

        for (int i = pos; i < arr.length; i++) {
            DFS(arr, i, curSum + arr[i], sum);
            cur.removeLast();
        }
    }

    public List<List<Integer>> getResult(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return result;
        }
        for (int i = 0; i < arr.length; i++) {
            cur.clear();
            DFS(arr, i, arr[i], target);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 6, 4, 2, 7};
        GettingList2 m = new GettingList2();
        List<List<Integer>> result = m.getResult(arr, 7);
        System.out.println(result);
    }
}