package Algorithm.dynamic;

import Algorithm.comprehensive.lsg.LSG;
import Top100.BackTrack;

/**
 * @author 蔚蔚樱
 * @version 1.0
 * @date 2019-11-25 16:42
 * @author—Email micromicrohard@outlook.com
 * @description 求数组中元素之和为指定值
 * 1、给定只包含整数的数组 array, 求数组中是否存在某些值相加等于 Target(数组数据可以无限重复选择)
 *
 * 示例：
 * 给定数组 array=[1,3,6,8,5] 和 给定的目标值 target=9
 * 比如符合给定数组和目标值的序列为：
 * [[1,1,1,6],
 * [1,8],
 * [3,6],
 * [1,3,5],
 * [1,1,1,1,5]]
 * [1,1,1,1,1,1,1,1,1]]
 * [1,1,3,1,3]]
 * [3,3,3]]
 */

public class CombinationNum_Dynamic implements LSG, BackTrack {

    // 求数组中是否存在某些值相加等于 Target
    public boolean verify(int[] array, int target) {
        if (array == null || array.length == 0) {
            return false;
        }
        // 可能存在负数情况，所以需要进行判断
        int size = target >= 0 ? target : -target;
        boolean[] answer = new boolean[size + 1];
        answer[0] = true;

        for (int i = 1; i <= size; i++) {
            for (int coin : array) {
                if (i - coin >= 0) {
                    answer[i] = answer[i - coin];
                }
                // 已满足条件
                if (answer[i]) {
                    break;
                }
            }
        }
        return answer[size];
    }


    public int LargestSumOfGap(int[] array) {
        return 0;
    }

    public int[][] Solution(int[] array, int target) {

        return new int[0][];
    }
}