let n' be the length of the array.

greedy. suppose we can form any integer in [0,m) using the first j numbers, let x be the (j+1)-th number. if x<=m, we can expand [0,m) to [0,m)+[x,x+m)=[0,x+m), otherwise greedily add a new number m, and expand to [0,2m). using O(log n) integers are sufficient, so time O(n'+log n).

We can get O(n') using bit tricks.

let k be the number of strings. 2D knapsack. O(nmk).

1. let k be the number of strings. 2D knapsack. O(nmk).

2. O~(max{n,m}^{8/3}). See my article https://leetcode.cn/problems/ones-and-zeroes/solutions/3041330/geng-kuai-de-omaxnm83de-suan-fa-by-hqztr-nldf/

Remark. faster algorithms for 2D subset sum with maximum cardinality?

1. O(n^2) by double pointers, enumerate one number.

2. we can reduce this problem to the tripartite version of 259. 3Sum Smaller, wlog assume a[i]<=a[j]<=a[k], can form a triangle iff a[i]+a[j]>a[k], i.e. a[i]+a[j]-a[k]>0. use a counting argument. O(n+U log U).

note. is this problem 3sum-hard?

if we allow negative edge weights (which doesn't make sense in geometry), we can reduce the tripartite version of 3sum to the tripartite version of this problem.

note. this problem is 3sum-hard.

1. If we allow negative edge weights (which doesn't make sense in geometry), we can reduce the tripartite version of 3sum to the tripartite version of this problem.

2. We can reduce 3sum to this problem, by first count the number of solutions once, then add each number by eps and count again. If the count differs then there's a 3sum solution.

Hamiltonian path.

Counting Hamiltonian path on grid.

1. dfs.

2. state-compressed DP.

2. state-compressed DP using connectivity on the boundary. 2^{O(min{n,m})}.

knapsack/subset sum. O~(t^1.5). See my article https://leetcode.cn/problems/length-of-the-longest-subsequence-that-sums-to-target/solutions/3041311/geng-kuai-de-ot15de-suan-fa-by-hqztrue-47yj/

Remark. better algorithm?

O(L).

Consider the rows and cols separately. O(sort(hBars.length+vBars.length)).

DP. Let f[i] denote the optimal cost to buy items i~n. monotone queue. O(n).

O(nm).