## Monday, August 8, 2016

[Solution]

lookup[k][j] = lookup[k – 1][t] && (nums[j] – nums[t]) in nums[] && (nums[j] – nums[t])的index和那k – 1个数不同, where t ∈ [0, j)
Base case: lookup[2][j] = true
time: O(k * n * n)
space: O(k * n * k), 因为对于每个lookup[k][j]都要存下k个数的index以防止后面使用重复的index.
`  ``public` `boolean` `kIndex(``int``[] nums, ``int` `k) {`
`    ``if` `(nums == ``null` `|| nums.lenght == ``0` `|| k == ``0``) {`
`      ``return` `false``;`
`    ``}`

`    ``int` `n = nums.length;`
`    ``Map<Integer, List<Integer>> map = ``new` `HashMap<>();`
`    ``Map<Integer, Map<Integer, Set<Integer>>> indexMap = ``new` `HashMap<>();`
`    ``for` `(``int` `i = ``0``; i < n; i++) {`
`      ``map.putIfAbsent(nums[i], ``new` `ArrayList<>());`
`      ``map.get(nums[i]).add(i);`
`    ``}`

`    ``int``[][] lookup = ``new` `int``[k + ``1``][n];`
`    ``for` `(``int` `j = ``0``; j < n; j++) {`
`      ``lookup[``2``][j] = ``true``;`
`      ``indexMap.putIfAbsent(``2``, ``new` `HashMap<>());`
`      ``indexMap.get(``2``).putIfAbsent(nums[j], ``new` `HashSet<>());`
`      ``indexMap.get(``2``).get(nums[j]).add(j);`
`    ``}`

`    ``for` `(``int` `i = ``3``; i <= k; i++) {`
`      ``for` `(``int` `j = ``0``; j < n; j++) {`
`        ``for` `(``int` `t = ``0``; t < j; t++) {`
`          ``if` `(lookup[i - ``1``][t] && map.containsKey(nums[j] - nums[t])) {`
`            ``Set<Integer> set = indexMap.get(i - ``1``).get(nums[t]);`
`            ``int` `newIndex = -``1``;`
`            ``for` `(``int` `x : map.get(nums[j] - nums[t])) {`
`              ``if` `(!set.contains(x)) {`
`                ``newIndex = x;`
`                ``break``;`
`              ``}`
`            ``}`
`            ``if` `(newIndex != -``1``) {`
`              ``Set<Integer> newSet = ``new` `HashSet<>(set);`
`              ``newSet.add(newIndex);`
`              ``indexMap.putIfAbsent(i, ``new` `HashMap<>());`
`              ``indexMap.get(i).put(nums[j], newSet);`
`              ``lookup[i][j] = ``true``;`
`            ``}`
`          ``}`
`        ``}`
`      ``}`
`    ``}`
`    ``return` `lookup[k][n - ``1``];`
`  ``}`